題目連接配接:http://acm.hdu.edu.cn/showproblem.php?pid=2647
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();
}
}