POJ3687BUCU5968——标签球（中文版）——题解

标签球

• 标签球

时间限制&＃xff1a;1秒
空间限制&＃xff1a;256M

题目描述

有N个不同重量的球&＃xff0c;重量为1~N个单位。对球从1到N进行标记&＃xff0c;使得&＃xff1a;

1. 没有两个球具有相同的标签

2. 标签满足几个约束&＃xff0c;例如“标签为a的球比标签为b的球轻”

输入描述

第一行包含测试用例的数量。

对于每个测试用例&＃xff1a;

第一行包含空格隔开的两个整数$N(1\le N\le 200)$和$M(0\le M\le 40000)$&＃xff0c;分别表示球的数量和约束的数量

后面的$M$行&＃xff0c;每行都包含空格隔开的两个整数$a$和$b$&＃xff0c;表示标签为$a$的球比标签为$b$的球轻$(1\le a,b\le N)$

每个测试用例前都有一个空行

输出描述

对于没个测试用例&＃xff0c;都单行输出标签1~N的球的重量。如果存在多种解决方案&＃xff0c;则输出标签为1的球的最小重量&＃xff0c;然后输出标签为2的球的最小重量&＃xff0c;以此类推……如果不存在解&＃xff0c;则输出-1。

样例一

输入

54 04 1
1 14 2
1 2
2 14 1
2 14 1
3 2


输出

1 2 3 4
-1
-1
2 1 3 4
1 3 2 4


本题步数输出小球的标签&＃xff0c;而是按标签输出小球的重量&＃xff0c;而且标签小的球的重量尽可能小。

可用采用下面两种方法解决

1. 建立正向图&＃xff0c;i&＃61;n…1&＃xff0c;j&＃61;n…1&＃xff0c;检查第1个出度为0的点t&＃xff0c;分配重量w[t]&＃61;i&＃xff0c;将弧尾节点的出度-1&＃xff0c;继续下一个循环。若没有出度为0的点&＃xff0c;说明有环&＃xff0c;退出。

2. 建立原图的逆向图。i&＃61;n…1&＃xff0c;j&＃61;n…1&＃xff0c;检查第1个入度为0的节点t&＃xff0c;分配重量w[t]&＃61;i&＃xff0c;将其邻接点的入度-1&＃xff0c;继续下一个循环。若没有入度为0的节点&＃xff0c;则说明有环&＃xff0c;退出。

#include
#include
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " &＃61; " << x << endl
#define fi(i, l, r) for (int i &＃61; l; i < r; i&＃43;&＃43;)
#define cd(a) scanf("%d", &a)
typedef long long ll;bool flag;
int n, m;
bool Map[250][250];
int in[250], w[250];void TopoSort() {flag &＃61; false;for (int i &＃61; n; i > 0; i--) {int t &＃61; -1;for (int j &＃61; n; j > 0; j--) {if (!in[j]) {t &＃61; j;break;}}if (t &＃61;&＃61; -1) {flag &＃61; true;return;}in[t] &＃61; -1;w[t] &＃61; i;for (int j &＃61; 1; j <&＃61; n; j&＃43;&＃43;) {if (Map[t][j]) {in[j]--;}}}
}int main() {int N;cin >> N;while (N--) {mem(Map), mem(in); // memsetcin >> n >> m;for (int i &＃61; 1; i <&＃61; m; i&＃43;&＃43;) {int u, v;scanf("%d%d", &u, &v);if (!Map[v][u]) {Map[v][u] &＃61; true;in[u]&＃43;&＃43;;}}TopoSort();if (flag) {cout << -1 << endl;continue;}for (int i &＃61; 1; i < n; i&＃43;&＃43;) {printf("%d ", w[i]);}cout << w[n] << endl;}return 0;
}


原创不易&＃xff0c;转载请附上原文链接哦~
Tisfy&＃xff1a;https://letmefly.blog.csdn.net/article/details/122618928