hdu 2647 Reward（拓扑排序）

题解：

题目大意：给你n个人，m个关系，表示a比b的奖金要多。问最少分配的奖金总数是多少。

思路：假如有这样一个图：

（ 箭头表示1比2奖金要多，1比5奖金要多）

 不难看出，标号3的那层都是888的奖金，标号2的那层都是889的奖金，标号1的那成是890的奖金，如果我们想要确定每个点权值的话，我们需要知道各个节点之间的全序关系，也就不难想到使用拓扑排序来做这个题，直接能够想到的方法就是直接拆点拆边，完成拓扑排序，如果不满足拓扑序输出-1.那么如果满足拓扑序呢？每个节点拆出来的层数来如何判断呢？每个点权值如何判断呢？这个时候我们其实不用一直憋牛角尖正向思维去做，我们不妨反着来考虑，反向建造图，也就相当于在原图中反着拆点拆边。

我们将图建成这样：

 这个时候度为0的点也就是分配888奖金的点，也就首先确定了一些点的点权值，接着我们拆边拓扑，也就不难想到，如果当前点u拆边之后使得一个点v的度为0，辣么这个点v的点权值也就比u的点权值多1.这个时候问题就全部解决辣.

最后处理代码问题：

10000*10000的邻接矩阵会超内存，我们使用邻接表实现即可：

#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>

using namespace std;
#define MAXN 10002 
#define INF 0x3f3f3f3f
struct Edge{
	int to,next,val;
}edge[MAXN*2];
int degree[MAXN],vis[MAXN];
int head[MAXN];
int edgeNum,n,m;
void init(){
	edgeNum=0;
	memset(vis,0,sizeof(vis));
	memset(degree,0,sizeof(degree));
	memset(head,-1,sizeof(head));
} 
void addEdge(int u,int v,int w){
	Edge e = {v,head[u],w};
	edge[edgeNum]=e;
	head[u]=edgeNum++;
}
int main(){
	
	while(scanf("%d%d",&n,&m)!=EOF){
		init();
		for(int i=0;i<m;i++){
			int a,b;
			scanf("%d%d",&a,&b);
			addEdge(b,a,i);//反向边 
			degree[a]++;//入度为0 
		}
		queue<int>q;
		int ans[MAXN];
		int sum=0;
		for(int i=1;i<=n;i++){
			if(degree[i]==0){
				q.push(i);
				ans[i]=888;	
				sum++;
				vis[i]=1;
			}
		}
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int i=head[u];i!=-1;i=edge[i].next){
				int v=edge[i].to;
				degree[v]--;
				
				if(degree[v]==0&&!vis[v]){
					vis[v]=1;
					sum++;
					ans[v]=ans[u]+1;
					q.push(v);
				}
			}
		}
		if(sum==n){
			int tol=0;
			for(int i=1;i<=n;i++)
			tol+=ans[i];
			printf("%d\n",tol);
		}else {
			printf("-1\n");
		}
		
	}
	
	return 0;
}