题意是求一系列盒子,给出相同数量不同重量的球,再满足题目所给轻重关系下让编号小的盒子里的球的重量最轻.
注意要反向建图,博主也不明白为什么..
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <vector> using namespace std; int b[205][205]; int c[205]; int indegre[205]; int n; int exi; void toposort() { int i, j = 0; priority_queue<int, vector <int>, less<int> >a; for (i = 1; i <= n; i++) { if(indegre[i]==0){a.push(i);j++;} } int e = n; if (a.empty()) { exi = 0; return; } while (!a.empty()) { int x = a.top(); a.pop(); c[x] = e--; for(i=1; i<=n; i++) { if(b[x][i]) { indegre[i]--; if(indegre[i]==0) { j++; a.push(i); } } } } if (j < n) { exi = 0; } return; } int main() { int t; scanf("%d", &t); int k; while (t--) { scanf("%d%d", &n, &k); int i, j; exi = 1; memset(b, 0, sizeof(b)); memset(indegre, 0, sizeof(indegre)); int book[205][205]={0}; for (i = 0; i < k; i++) { int x, y; scanf("%d%d", &x, &y); if(book[x][y]==0) {indegre[x]++;book[x][y]=1;} b[y][x] = 1; } toposort(); if (exi) { printf("%d", c[1]); for (i = 2; i <= n; i++) { printf(" %d", c[i]); } printf("\n"); } else { printf("-1\n"); } } return 0; }
