POJ3687 Labeling Balls(拓扑)

题目链接

题目大意:

N个球,从1~N编号,质量不同,范围1~N,无重复。给出小球间的质量关系(<), 要求给每个球贴标签,标签表示每个球的质量。按编号输出每个球的标签。如果解不唯一,按编号小的质量小排。

分析:

通过一组数据发现理解错题意了。

1

5 4
1 4
4 2
5 3
3 2
答案应当是:
1 5 3 4 2

当解有多组时,编号小的质量小,这一条件不太好用。所以就反向建图,按编号从大到小,找质量最大的。这样,小标签就都留给了编号小的。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cstring>
#include <queue> using namespace std; const int maxn = +; bool G[maxn][maxn];
int n, m, ind[maxn], a[maxn]; bool topsort() {
for(int i=n; i>=; i--) {
int k;
for(k=n; k>=; k--)
if(ind[k] == ) {
a[k] = i;
ind[k]--;
break;
} if(k < ) return false; for(int j=; j<=n; j++) {
if(G[k][j]) ind[j]--;
}
} return true;
} int main() {
int T, u, v; scanf("%d", &T); while(T--) {
scanf("%d%d", &n, &m); memset(G, , sizeof(G));
memset(ind, , sizeof(ind)); for(int i=; i<m; i++) {
scanf("%d %d", &v, &u);
if(!G[u][v]) {
G[u][v] = true;
ind[v]++;
}
} if(topsort()) {
for(int i=; i<=n; i++) {
if(i != n) printf("%d ", a[i]);
else printf("%d\n", a[i]);
}
}
else printf("-1\n");
} return ;
}
上一篇:BurpSuite的使用总结


下一篇:[PAT]数列求和(20)