贴代码
#include <iostream> #include <cstdio> #include <queue> #include <cstring> using namespace std; const int Maxn=10000+10; int money[Maxn]; int head[Maxn],ind[Maxn]; int n,m,num; int x,y,ans,sum; struct Line { int next,to; }line[Maxn*2];//邻接表储存边 void add(int from,int to) { line[++num].to=to; line[num].next=head[from]; head[from]=num; ind[to]++; }//邻接表处理加边 void topo() { queue <int> Q; for(int i=1;i<=n;i++) if(ind[i]==0) Q.push(i),sum++,ans+=money[i];//如果入度为0，就入队； while(!Q.empty())//用队列来处理数据，也可以用栈； { int u=Q.front(); Q.pop(); for(int i=head[u];i;i=line[i].next) { money[line[i].to]=max(money[line[i].to],money[u]+1); if(--ind[line[i].to]==0) { Q.push(line[i].to); ans+=money[line[i].to]; sum++; } } } } int main() { while(scanf("%d%d",&n,&m)!=EOF) { memset(head,0,sizeof head); memset(money,0,sizeof money); sum=0,ans=0,num=0; memset(line,0,sizeof line); memset(ind,0,sizeof ind);//注意每一次处理要清空之前的数据 for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(y,x);//建立一条从y至x的边 } for(int i=1;i<=n;i++) money[i]=888; topo(); if(sum!=n) printf("-1\n");//如果sum!=n就说明拓扑无法完成，该图不是DAG,图中有矛盾 else printf("%d\n",ans); } return 0; }