hdu2647 拓扑序

题意：年终要给 n 个员工发奖金，每个人的起始金额是888，有些人觉得自己做的比另一个人好所以应该多得一些钱，问最少需要花多少钱，如果不能满足所有员工的要求，输出 -1

拓扑排序，从奖金少的向奖金多的建边，这样从奖金少的开始可以定 888 。对所有最开始入度为 0 的点开始，全发 888 ，由于加入队列的点的奖金数额其实是从小到大的，所以当某个点入度减为 0 时，就直接用这次用来更新的点的奖金+1 作为新一个点的奖金就行。

 #include<stdio.h>

 #include<string.h>

 #include<queue>

 using namespace std;

 const int maxn=1e4+;

 const int maxm=2e4+;

 int ans,n;

 int id[maxn],num[maxn];

 int head[maxn],point[maxm],nxt[maxm],size;

 void add(int a,int b){

     point[size]=b;

     nxt[size]=head[a];

     head[a]=size++;

     id[b]++;

 }

 bool topo(){

     ans=;

     queue<int>q;

     for(int i=;i<=n;++i)if(!id[i]){

         q.push(i);

         num[i]=;

     }

     int cnt=;

     while(!q.empty()){

         int u=q.front();q.pop();

         ans+=num[u];

         cnt++;

         for(int i=head[u];~i;i=nxt[i]){

             int j=point[i];

             id[j]--;

             if(!id[j]){

                 num[j]=num[u]+;

                 q.push(j);

             }

         }

     }

     if(cnt==n)return ;

     return ;

 }

 int main(){

     int m;

     while(scanf("%d%d",&n,&m)!=EOF){

         memset(head,-,sizeof(head));

         size=;

         memset(id,,sizeof(id));

         while(m--){

             int a,b;

             scanf("%d%d",&a,&b);

             add(b,a);

         }

         if(topo())printf("%d\n",ans);

         else printf("-1\n");

     }

     return ;

 }

巴特西

hdu2647 拓扑序

最新文章

热门文章