hdu2647reward

Input
One line with two integers n and m ,stands for the number of works and the number of demands .(n<=10000,m<=20000)
then m lines ,each line contains two integers a and b ,stands for a's reward should be more than b's.
 

Output
For every case ,print the least money dandelion 's uncle needs to distribute .If it's impossible to fulfill all the works' demands ,print -1.
  

比较需要注意的是需要倒着插入,为什么呢?奖励至少高一元,且求最少花费,否则就是最大的花费了==
#include <string.h>
#include <stdio.h>
#include <iostream>
using namespace std;
struct note
{
    int to;
    int next;
};
note edge[20005];
int head[20005],ip,iq;
int indegree[20005],queue[20005],money[20005];
void add(int u,int v)
{
    edge[ip].to=v,edge[ip].next=head[u],head[u]=ip++;
}
int main()
{
    int m,n,a,b;
    while(~scanf("%d%d",&n,&m))
    {
         memset(indegree,0,sizeof(indegree));
        // memset(queue,0,sizeof(queue));
         memset(head,-1,sizeof(head));
         for(int i=0;i<=n;i++) money[i]=888;
         while(m--)
         {
             scanf("%d%d",&a,&b);
             add(b,a);
             indegree[a]++;
         }
         ip=iq=0;
         for(int i=1;i<=n;i++)
         {
             if(indegree[i]==0) queue[iq++]=i;
         }
         for(int i=0;i<iq;i++)
            for(int k=head[queue[i]];k!=-1;k=edge[k].next)
            {
                if(!--indegree[edge[k].to])
                {
                    queue[iq++]=edge[k].to;
                    money[edge[k].to]=money[queue[i]]+1;
                }
            }
        int sum=0;
        if(iq==n)
        {
            for(int i=1;i<=n;i++) sum+=money[i];
            printf("%d\n",sum);
        }
        else printf("-1\n");
    }
    return 0;
}


全部评论

相关推荐

07-17 11:27
门头沟学院 Java
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务