首页 > 代码库 > poj3687(Labeling Balls)
poj3687(Labeling Balls)
题目大意:
给你N个球的重量比较,输出1->N位置球的重量(记住是球的重量,不是按照球重量大小输出序号,球的重量大小也是1->n)。如果无法判断输出-1.
解题思路:
拓扑排序,记录较小的编号球的入度,依次n--赋值入度为零的编号球。
代码:
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 /***************************************/ 21 const int INF = 0x7f7f7f7f; 22 const double eps = 1e-8; 23 const double PIE=acos(-1.0); 24 const int d1x[]= {0,-1,0,1}; 25 const int d1y[]= {-1,0,1,0}; 26 const int d2x[]= {0,-1,0,1}; 27 const int d2y[]= {1,0,-1,0}; 28 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 29 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 30 /***************************************/ 31 void openfile() 32 { 33 freopen("data.in","rb",stdin); 34 freopen("data.out","wb",stdout); 35 } 36 /**********************华丽丽的分割线,以上为模板部分*****************/ 37 int cnt1[205],cnt2[205]; 38 int topol[205]; 39 int adj[205][205],adi[205][205]; 40 int dui[205],re[205]; 41 int topo(int n) 42 { 43 int i,j,k,d=0,z=-1,x,m; 44 m=n; 45 for(i=1; i<=n; i++) 46 for(j=n; j>=1; j--) 47 { 48 if(cnt2[j]==0) 49 { 50 cnt2[j]=-1; 51 re[j]=m--; 52 topol[d++]=j; 53 for(k=1; k<=n; k++) 54 if(adi[k][j]) 55 { 56 adi[k][j]=0; 57 cnt2[k]--; 58 } 59 break; 60 } 61 } 62 if (d!=n) 63 return 0; 64 for(j=1; j<=n; j++) 65 { 66 if(j!=n) 67 printf("%d ",re[j]); 68 else 69 printf("%d\n",re[j]); 70 } 71 return 1; 72 } 73 int main() 74 { 75 int cas; 76 scanf("%d",&cas); 77 while(cas--) 78 { 79 int i,a,b; 80 int m,n,c=1; 81 scanf("%d%d",&m,&n); 82 memset(topol,0,sizeof(topol)); 83 memset(cnt1,0,sizeof(cnt1)); 84 memset(cnt2,0,sizeof(cnt2)); 85 memset(adj,0,sizeof(adj)); 86 memset(adi,0,sizeof(adi)); 87 while(n--) 88 { 89 scanf("%d%d",&a,&b); 90 if (!adj[a][b]) 91 { 92 adj[a][b]=1; 93 adi[a][b]=1; 94 cnt1[b]++; 95 cnt2[a]++; 96 } 97 } 98 c=topo(m); 99 if (c==0)100 printf("-1\n");101 }102 return 0;103 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。