首页 > 代码库 > poj3687（Labeling Balls）

poj3687（Labeling Balls）

2024-07-11 19:17:18   223人阅读

题目大意：

    给你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 }
View Code

 


联系
我们