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.
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;
}
投递荣耀等公司10个岗位 >
