Labeling Balls
Windy has N balls of distinct weights from 1 unit to N units. Now he tries to label them with 1 to N in such a way that:
1. No two balls share the same label.
2. The labeling satisfies several constrains like "The ball labeled witha is lighter than the one labeled with b".
Can you help windy to find a solution?
Input
The first line of input is the number of test case. The first line of each test case contains two integers, N (1 ≤ N ≤ 200) and M (0 ≤ M ≤ 40,000). The next M line each contain two integers aand b indicating the ball labeled with a must be lighter than the one labeled with b. (1 ≤ a, b ≤ N) There is a blank line before each test case.
Output
For each test case output on a single line the balls' weights from label 1 to label N. If several solutions exist, you should output the one with the smallest weight for label 1, then with the smallest weight for label 2, then with the smallest weight for label 3 and so on... If no solution exists, output -1 instead.
Sample Input
5
4 0
4 1
1 1
4 2
1 2
2 1
4 1
2 1
4 1
3 2
Sample Output
1 2 3 4
-1
-1
2 1 3 4
1 3 2 4
Source
POJ Founder Monthly Contest – 2008.08.31, windy7926778
题目类型：拓扑排序
算法分析：这里若将重量小的球向重量大的球连边，则不能保证正确性。所以反过来想，将重量大的球向重量小的球连边，每次给标号尽可能大的，入度为0的点递减赋值，这样就能保证标号小的球重量尽可能小。注意图中可能出现平行边，可以处理也可以不处理
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
/************************************************* Author :supermaker Created Time :2016/3/20 18:03:36 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 200 + 66; vector <int> edge[maxn]; int n, m, ind[maxn], ans[maxn]; bool vis[maxn], hasedge[maxn][maxn]; int Topo () { memset (vis, false, sizeof (vis)); for (int cnt = n; cnt >= 1; cnt--) { int pos = -1; for (int i = n; i >= 1; i--) if (!ind[i] && !vis[i]) { pos = i; break; } if (pos == -1) return -1; for (int i = 0; i < edge[pos].size (); i++) ind[edge[pos][i]]--; vis[pos] = true; ans[pos] = cnt; } return 1; } int main() { //CFF; //CPPFF; int t; scanf ("%d", &t); while (t--) { scanf ("%d%d", &n, &m); for (int i = 0; i < maxn; i++) edge[i].clear (); memset (ind, 0, sizeof (ind)); memset (hasedge, false, sizeof (hasedge)); for (int i = 1; i <= m; i++) { int u, v; scanf ("%d%d", &u, &v); if (!hasedge[v][u]) { ind[u]++; edge[v].push_back (u); hasedge[v][u] = true; } } int res = Topo (); if (res == -1) puts ("-1"); else { for (int i = 1; i <= n; i++) { if (i == 1) printf ("%d", ans[i]); else printf (" %d", ans[i]); } puts (""); } } return 0; } |
- « 上一篇：poj1128
- poj3026：下一篇 »