can imp ron case lin int ould pos
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9799 Accepted Submission(s): 3131
- #include < iostream > #include < cstring > #include < cstdio > #include < vector > #include < queue >
- using namespace std;
- const int N = 10000 + 15;
- int n,
- m,
- in[N],
- val[N];
- vector < int > edge[N];
- void Solve_question() {
- int ans = 0,
- cnt = 0;
- queue < int > Q;
- for (int i = 1; i <= n; i++) if (!in [i]) {
- Q.push(i);
- val[i] = 888;
- }
- while (!Q.empty()) {
- int u = Q.front();
- Q.pop();
- cnt++;
- for (int i = 0; i < (int) edge[u].size(); i++) {
- int v = edge[u][i];
- if (--in [v] == 0) {
- Q.push(v);
- val[v] = val[u] + 1;
- }
- }
- }
- if (cnt < n) puts("-1");
- else {
- for (int i = 1; i <= n; i++) ans += val[i];
- printf("%d\n", ans);
- }
- }
- void Input_data() {
- for (int i = 1; i <= n; i++) edge[i].clear(),
- val[i] = in[i] = 0;
- int u,
- v;
- for (int i = 1; i <= m; i++) {
- scanf("%d %d", &u, &v); in [u]++;
- edge[v].push_back(u);
- }
- }
- int main() {
- while (scanf("%d %d", &n, &m) == 2) {
- Input_data();
- Solve_question();
- }
- }
HDU-2647 Reward(拓扑排序)
来源: http://www.bubuko.com/infodetail-2273664.html