新浪微博 登陆  注册   设为首页 加入收藏

学PHP >> 设计模式与算法 >> HDU2647(逆向拓扑排序)

HDU2647(逆向拓扑排序)

查看次数9228 发表时间2012-08-01 00:04:43

 
package D0731;

/*
 * 题目大意:
 * 发奖金,如果能够实现每个人的需求就发,需求要满足拓扑排序。
 * 这个题目使用逆向的拓扑图更方便
 * 如果需求满足拓扑排序结果为n*888+(n/2*(n-1))
 * */
import java.util.*;
import java.io.*;

public class HDU2647 {

	static int n, m;
	static int[] indegree;// 顶点的入度
	static int index;// 拓扑排序的长度
	static List<ArrayList<Integer>> G = new ArrayList<ArrayList<Integer>>();// 邻接表
	static Queue<Integer> que;

	// /拓扑排序
	private static int topSort() {
		int[] rewards = new int[n + 1];// 工资-888
		int ans = 0;
		index = 0;
		que = new LinkedList<Integer>();

		for (int i = 1; i <= n; i++)
			if (indegree[i] == 0)
				que.add(i);

		while (!que.isEmpty()) {
			int v = que.poll();
			index++;
			for (int i : G.get(v)) {
				indegree[i]--;
				if (indegree[i] == 0) {
					que.add(i);
					rewards[i] = rewards[v] + 1;
					ans += rewards[i];
				}
			}
		}
		return ans;
	}

	public static void main(String[] args) throws IOException {
		StreamTokenizer st = new StreamTokenizer(new BufferedReader(
				new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

		while (st.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) st.nval;
			st.nextToken();
			m = (int) st.nval;
			indegree = new int[n + 1];
			G.clear();
			for (int i = 0; i <= n; i++)
				G.add(new ArrayList<Integer>());
			while (m-- > 0) {
				st.nextToken();
				int u = (int) st.nval;
				st.nextToken();
				int v = (int) st.nval;
				// 建立逆向的方向拓扑图,
				if (!G.get(v).contains(u)) {// 注意重边
					G.get(v).add(u);
					indegree[u]++;
				}
			}

			int ans = topSort();
			if(index==n)out.println(ans+n*888);
			else out.println(-1);
		}
		out.flush();

	}

}


(转发请注明转自:学PHP)    


  相关推荐



1楼 Skip说: 2016-06-07 08:42:03
Any particular reason for Cork County, Ireland? Not that I disagree, I went in June and it was fatncstiaally gorgeous. It just seems specific, just curious.Egypt is great, definitely a must see. And I totally agree about TAR, Orlando, New York and Hawaii!
2楼 Lyndee说: 2016-09-09 14:26:58
Do they still have the &quot;small kiunseds&qnot; boxes at some of the LRT stations? I thought those were so cute&#8230; until people kept destroying them, of course. Sigh. I&#39;d love to see fun stuff like that at train stations over here, and I want to believe that they wouldn&#39;t get wrecked, but who knows.

  发表评论
昵称:
(不超过20个字符或10个汉字)
内容: