1257.Problem E. SDNU ACM/ICPC TEAM
Description
Lulichuan is the captain of SDNU ACM/ICPC TEAM, he have many team members, Their ability has a sequence from 1 to N, now , lulichuan want to labeled them from 1 to N in this way
a. Two member have different label
b. The labeling satisfies several constrains like "The member labeled with x is lower than the one labeled with y”.
Input
The first line is T, T is TestCase(0 < T <= 1000)
The first line of each testcase is two number N, M(0 < 500 < n, 0 < M < 100000)
The next M line each contain two integers x and y indicating the member labeled with x must be lower than the one labeled with y. (1 ≤ x, y ≤ N)
Output
For each test case output on a single line the member' ability from label 1 to label N. If several solutions exist, you should output the one with the lowest ability for label 1, then with the lowest ability for label 2 and so on... If no solution exists, output -1 instead.
Sample Input
54 04 11 14 21 22 14 12 14 13 2
Sample Output
1 2 3 4-1-12 1 3 41 3 2 4
这道题的大体意思：：陆厉川这个zz要给队员打标记~~一共n个人，分别拥有着1~n的能力值，打标记的话~一个是由m个要求：：第x个的能力一定要比y弱！！，另一个是在满足上个的情况下从1开始~尽量让他们拥有他们能拥有的最小能力值~，
意思就是先让1的能取到的最小能力值不论方法先取到~再是从2开始。。。以此类推。
这道题一共有两个注意的地方~一个是需要用到反向topo排序：：因为决定排序的一个原因是最后的比较的最强能力者决定~~就比如如果有条件3一定要比2弱~~那么决定排列先后的是2而不是3。
还有就是~按照要求排列出来后，得出来的结果：：其实是每个能力者对应的序号~~就像是把序号按要求排列后~从1到n赋给能力者~~但是注意的是~他最后要求的是按照序号来输出能力~__~ 很烦~。
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<functional>
#include<cstring>
using namespace std;
priority_queue<int>q;
vector<int>ma[100005];
int out[100005];
int ans1[100005];
int ans[100005];
int cnt = 1;
int m, n;
void topo()
{
for (int s = 1; s <= m; s++)
{
if (out[s] == 0)
{
q.push(s);
// cout << s << endl;
}
}
while (!q.empty())
{
int t = q.top();
q.pop();
// cout << cnt<<" "<<t << endl;
ans1[t] = cnt;//这是序号对应能力
ans[cnt--] = t;//这是能力对应序号
for (int s = 0; s < ma[t].size(); s++)
{
out[ma[t][s]]--;
if (out[ma[t][s]] == 0)
{
q.push(ma[t][s]);
}
}
}
}
int main()
{
int te;
scanf("%d", &te);
while (te--)
{
memset(out, 0, sizeof(out));
scanf("%d%d", &m, &n);
cnt = m;
for (int s = 1; s <= m; s++)
{
ma[s].clear();
}
while (n--)
{
int a, b;
scanf("%d%d", &a, &b);
ma[b].push_back(a);
out[a]++;
}
topo();
if (cnt != 0)
{
cout << "-1" << endl;
}
else
{
for (int s = 1; s<m; s++)
{
printf("%d ", ans1[s]);
}
cout << ans1[m] << endl;
}
}
return 0;
}
京公网安备 11010502036488号