计蒜课 https://nanti.jisuanke.com/t/16957
[代码] :
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 1e5 + 10;
- const int mod = 142857;
- int t,n,m,k,x,u,v,w,num;
- vector<pair<int,int>> G[maxn];
- int inDeg[maxn], dp[maxn];
- int virus[maxn];
- queue<int> q;
- void topSort()
- {
- while(!q.empty()) q.pop();
- for(int i=1;i<=n;i++) if(!inDeg[i]) q.push(i);
- while(!q.empty())
- {
- int now = q.front();
- q.pop();
- for(int i=0;i<G[now].size();i++)
- {
- int nxt = G[now][i].first;
- if(--inDeg[nxt] == 0) q.push(nxt);
- dp[nxt] = max(dp[nxt], dp[now]+G[now][i].second);
- }
- }
- }
- int main()
- {
- scanf("%d",&t);
- while(t--)
- {
- scanf("%d%d",&n,&m);
- memset(inDeg,0,sizeof(inDeg));
- memset(dp,0,sizeof(dp));
- for(int i=1;i<=n;i++) G[i].clear();
- while(m--)
- {
- scanf("%d%d%d",&u,&v,&w);
- G[u].push_back(make_pair(v,w));
- inDeg[v]++;
- }
- topSort();
- int maxx = -1;
- for(int i=1; i<=n; i++) maxx = max(maxx,dp[i]);
- printf("%d\n",maxx);
- }
- }
来源: http://www.bubuko.com/infodetail-2642042.html