2 1 1 2 2 2 1 2 2 1
1777 -1
拓撲排序+優先隊列
#include"stdio.h" #include"string.h" #include"queue" using namespace std; #define N 10005 #define M 20005 struct st { int x,v; //存點坐標和價值 friend bool operator<(st a,st b) { return a.v>b.v; } }; struct node { int v,next; }bian[M]; int indeg[N],e; int head[N]; void add(int u,int v) //存邊的信息 { bian[e].v=v; bian[e].next=head[u]; head[u]=e++; } int top_sort(int n) { int mark[N],i,x,cnt=0,sum=0,v; memset(mark,0,sizeof(mark)); priority_queueq; st cur,next; cur.v=888; for(i=1;i<=n;i++) { if(indeg[i]==0) { cur.x=i; mark[i]=1; cnt++; q.push(cur); } } while(!q.empty()) //每次找出入度為零的點,更新它指向的點信息。 { cur=q.top(); q.pop(); sum+=cur.v; x=cur.x; for(i=head[x];i!=-1;i=bian[i].next) { v=bian[i].v; indeg[v]--; if(indeg[v]==0&&!mark[v]) { mark[v]=1; cnt++; next.v=cur.v+1; next.x=v; q.push(next); } } } if(cnt==n) return sum; return -1; } int main() { int n,m,i,v,u; while(scanf("%d%d",&n,&m)!=-1) { memset(head,-1,sizeof(head)); memset(indeg,0,sizeof(indeg)); e=0; while(m--) { scanf("%d%d",&v,&u); add(u,v); indeg[v]++; } int t=top_sort(n); printf("%d\n",t); } return 0; }