http://poj.org/problem?id=3687
题意:给定几个标签球的重量大小关系,求每个球是第几重的(即每个球在所有球的重量中由小到大排名是多少)。
(输出是每个球第几重,而不是几号球比几号球重!)。一开始理解错了QAQ
思路:反向拓扑+优先队列。因为正向不好用。。。所以我们连边的时候由重的指向轻的。。这样最先出队的就是最重的。。和上道题差不多?
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 |
/* *********************************************** Author :111qqz Created Time :2015年12月19日 星期六 16时32分59秒 File Name :code/poj/3687.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> #define fst first #define sec second #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define ms(a,x) memset(a,x,sizeof(a)) typedef long long LL; #define pi pair < int ,int > #define MP make_pair using namespace std; const double eps = 1E-8; const int dx4[4]={1,0,0,-1}; const int dy4[4]={0,-1,1,0}; const int inf = 0x3f3f3f3f; const int N=203; int n,m; bool conc[N][N]; bool ok; int in[N]; int ans[N]; void topo() { priority_queue<int >q; for ( int i = 1 ; i <= n ; i++) if (in[i]==0) q.push(i); int cnt = n ; while (!q.empty()) { int v = q.top(); q.pop(); ans[v] = cnt--; for ( int i =1 ; i <= n ; i++) { if (!conc[v][i]) continue; in[i]--; if (in[i]==0) q.push(i); } } // cout<<"cnt:"<<cnt<<endl; if (cnt!=0) { puts("-1"); } else { for ( int i =1 ; i <= n-1 ; i++) printf("%d ",ans[i]); printf("%d\n",ans[n]); } } int main() { #ifndef ONLINE_JUDGE freopen("code/in.txt","r",stdin); #endif int T; cin>>T; while (T--) { scanf("%d %d",&n,&m); ok = true; ms(conc,false); ms(in,0); while (m--) { int x,y; scanf("%d %d",&x,&y); if (x==y) ok = false; if (conc[y][x]) continue; //重边. conc[y][x] = true; in[x]++; } if (ok) { topo(); } else { puts("-1"); } } #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } |
说点什么
您将是第一位评论人!