2021/8/16 22:17
题意:给出一个有向图,并说明了只有一个源点和一个汇点,要求求出所有关键活动,并计算完成该工程的最短时间。
思路:求出所有关键活动,我们应该想到,虽然源点汇点规定了只有一个,但是关键路径会有多条阿,在任何一条关键路径上的任何结点,都属于关键活动,全部都要输出(没看懂题意的我真的做了个寂寞😶)。
首先可以分析得出,题目考察了拓扑排序的应用,直接套拓扑排序的模板,判断该工程是否可以完成,如果不可以则直接输出unworkable project(可惜这一个测试点没有😶)。可以完成该工程的话之后就是求其最短时间(最长路径),这里就可以直接dfs来求解了。要考虑的点在于如何对其关键活动的存储,因为题意是要求两个点两个点输出,而且还要按递增的关系,所以在存的时候我们可以用pair来存储每条边的两个端点,再用一个set容器将其嵌套,则可以不用考虑排序的问题。这里用了vector容器作为过渡,如果最大的路径刷新,则也要清空set容器,如果路径长度相同,也需要把得到的关键活动存入set容器当中。
C++ 代码
#include<iostream>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
typedef pair<int,int> PII;
const int N = 205;
int e[N],w[N],ne[N],h[N],idx;
int d[N], copy_d[N];
int q[N];
int ans;
int n, m;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool topSort()
{
int hh = 0, rr = 0;
for(int i = 1; i <= n; i++)
{
if(d[i] == 0)
q[rr++] = i;
}
while(hh < rr)
{
int t = q[hh++];
for(int i = h[t]; ~i; i = ne[i])
{
if(--d[e[i]] == 0)
q[rr++] = e[i];
}
}
return rr == n;
}
vector<PII> path;
set<PII> s;
void dfs(int u, int cost)
{
if(h[u] == -1)
{
if(ans <= cost)
{
if(ans < cost)
s.clear();
ans = cost;
for(int i = 0; i < path.size(); i++)
{
s.insert(path[i]);
}
}
}
for(int i = h[u]; ~i; i = ne[i])
{
path.push_back({u, e[i]});
dfs(e[i], w[i]+cost);
path.pop_back();
}
}
int main()
{
while(cin >> n >> m)
{
memset(h,-1,sizeof(h));
memset(d,0,sizeof(d));
ans = 0;
while(m--)
{
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);
d[b]++;
}
memcpy(copy_d, d, sizeof(d));
if(topSort())
{
for(int i = 1; i <= n; i++)
{
if(copy_d[i] == 0)
dfs(i, 0);
}
cout << ans << endl;
for(auto t : s)
{
cout << t.first << "->" << t.second << endl;
}
}
else
cout << "unworkable project" << endl;
}
return 0;
}
大佬这个题在哪里啊?
啊不好意思,这个题目是我在我们学院题库里找到的,我也不太清楚具体题源😢,我把题目截了一下放了上来,希望对你有帮助