题目链接：HDU2647

题目大意：给一张n节点m条边的图，(n<=10000,m<=20000)。并且要求每次输入的u,v节点 v的价值大于u的价值。最终输出总价值的最小值。

解题思路：利用拓扑排序输出的序列价值要递增比较容易建图，这张m边有向图边的方向满足 (v,u):u的价值大于v的价值 这样一个偏序关系。关键点在于 反向建图 。

AC代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <utility>
using namespace std;

/* 邻接表存边以及相应的cost S = n*a1 + n*(n-1) * /2*d 10000*888 + 5000*9999 < int 答案不会爆int */

const int maxn = (int)1e4+5;

int book[maxn],n,m,u,v;
vector<int > Vertex[maxn];
queue<pair<int, int> > Q;

int TopSort () {
	int cost;
	for (int i = 1; i <= n; i++) {
		if(book[i] == 0) {
			Q.push(make_pair(i,888));
		}
	}
	
	while (!Q.empty()) {
		v = Q.front().first;
		cost = Q.front().second;
		Vertex[0].push_back(cost);
		Q.pop();
		for (vector<int>:: iterator it = Vertex[v].begin(); it != Vertex[v].end(); it++) {
			book[*it]--;
			if(book[*it] == 0) {
				Q.push(make_pair((*it), cost + 1));
			}
		}
	}
	
	if(Vertex[0].size() == n) {
		int sum = 0;
		for (vector<int>:: iterator it = Vertex[0].begin(); it != Vertex[0].end(); it++) {
			sum += (*it);
		}
		return sum;
	}
	return -1;
}

int main() {
	while (~scanf("%d%d",&n,&m)) {
		for (int i = 0; i <= n; i++) {
			Vertex[i].clear();
		}
		memset(book,0,sizeof(book));
		for (int i = 0; i < m; i++) {
			scanf("%d%d",&u,&v);  //value(u) > value(v)
			book[u]++;
			Vertex[v].push_back(u);
		}
		
		while (!Q.empty()) {
			Q.pop();
		}
		printf("%d\n",TopSort());
	}
	return 0;
}