HDOJ1811解题报告【拓扑排序正向反向】-白红宇

HDOJ1811解题报告【拓扑排序正向反向】

阅读量：4509 次

发布时间：2019-06-08

本文共 1449 字，大约阅读时间需要 4 分钟。

题目地址：

　　http://acm.hdu.edu.cn/showproblem.php?pid=1811

题目概述：

　　中文题就略了。

大致思路：

　　显然这是一个拓扑排序的问题，不过题中有两个点rating相等的情况，我们发现因为不关心最后的排序结果，所以用并查集合并一下相等的点这时候就是求一个有向图的拓扑序了。

　　题中conflict的情况是图中有环，uncertain的情况是所求排序不唯一，此时只需要将有向图反向，再求一遍拓扑序对比一下之前求的拓扑序，如果有差异则说明情况为uncertain，否则为OK。

代码：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
            8 #include 
            
              9 #include 
             
               10 #include 
              
                11 #include 
               
                 12 using namespace std; 13 14 #define sacnf scanf 15 #define scnaf scanf 16 #define maxn 10010 17 #define maxm 26 18 #define inf 1061109567 19 #define Eps 0.00001 20 const double PI=acos(-1.0); 21 #define mod 1000033 22 #define MAXNUM 10000 23 void Swap(int &a,int &b) { int t=a;a=b;b=t;} 24 int Abs(int x) { return (x<0)?-x:x;} 25 typedef long long ll; 26 typedef unsigned int uint; 27 28 struct node 29 { 30 int from,to; 31 char cmp; 32 } edge[maxn]; 33 34 vector
                
                  G[maxn]; 35 int in[maxn],ans[maxn],p[maxn],cnt,equals; 36 37 int found(int x) { return (p[x]==x)?x:p[x]=found(p[x]);} 38 39 void toposort(int n) 40 { 41 queue
                 
                   q; 42 for(int i=0;i

,greater

> q; 63 for(int i=0;i

') {G[a].push_back(c);in[c]++;}107 }108 /*for(int i=0;i

') {G[c].push_back(a);in[a]++;}126 }127 re_toposort(n);128 }129 //clock_t ed=clock();130 //printf("\n\nTime Used : %.5lf Ms.\n",(double)(ed-st)/CLOCKS_PER_SEC);131 return 0;132 }

转载于:https://www.cnblogs.com/CtrlKismet/p/6670133.html

你可能感兴趣的文章