题目链接
老板给员工发工资，每个人的基本工资都是888，然后还有奖金，然后员工之间有矛盾，有的员工希望比某员工的奖金多，老板满足了所以员工的这种心思，而且老板下午发的总工资最少，问最少是多少？比如 a b 表示a的工资比b要高(高一块钱)，当出现a b b c c a这种环的时候输出-1
拓扑排序
小指向大
邻接表建图
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 8 const int M = 1e4 + 10; 9 int head[M],into[M],n,m,cas,money[M];10 struct Edge{11 int to; //表示一条边上的大的结点(因为小指向大)编号12 int next; //表示边的编号13 }edge[M*2];//注意为两倍14 15 void init()16 {17 for (int i=1 ; i<=n ; i++){18 head[i]=-1;19 into[i]=0;20 money[i]=888;21 }22 }23 24 void addedge(int u(小),int v(大))//小指向大25 {26 edge[cas].to=v; //表示第cas条边的小的结点为v27 edge[cas].next=head[u]; //表示上一条以u为起点的边的编号,就是假设一个点有多个出度28 head[u]=cas++; //表示结点u所在的边的编号29 into[v]++; //入度30 }31 32 int topu()33 {34 queue que;35 int num=0,sum=0;36 for (int i=1 ; i<=n ; i++)37 if (into[i]==0)38 que.push(i);39 while (!que.empty()){40 int u=que.front();41 sum+=money[u];42 que.pop();43 num++;44 for (int i=head[u] ; i!=-1 ; i=edge[i].next){45 into[edge[i].to]--;46 if (into[edge[i].to]==0){47 que.push(edge[i].to);48 money[edge[i].to]=money[u]+1;49 }50 }51 }52 if (num!=n) return -1;53 return sum;54 }55 56 int main()57 {58 while (~scanf("%d%d",&n,&m)){59 init();60 cas=0;61 while (m--){62 int a,b;63 scanf("%d%d",&a,&b);64 addedge(b,a);65 }66 printf("%d\n",topu());67 }68 return 0;69 }
vector建图的表示，其实差不多
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 9 const int M = 1e4 + 10;10 int a[M],into[M],money[M],n,m;11 vector q[M];12 13 int topu()14 {15 memset(into,0,sizeof(into));16 for (int i=1 ; i<=n ; i++)17 for (int j=0 ; j