拓扑排序-白红宇

拓扑排序

阅读量：4319 次

发布时间：2019-06-06

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

有很多奇妙的题.....

题目VJ上做了些.

近期在POJ和HDU上做一些题,参考

HDU 1285 裸题不讲=w=很久以前用Vector建图的时候就A了......

HDU 2647 就是判断一下是否有拓扑序列(这个可以用强连通分量Tarjan做=w=但是拓扑排写起来比较简单...)

然后总代价就是按照排序层数(具体看程序,我们把能够同时存在于队列中的元素表上同一个dep)算....

1 #include 
      
         2 #include 
       
          3 #include 
        
           4    5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 10 #include 
             
               11 #include 
              
                12 #include 
                13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 17 typedef unsigned int uint; 18 typedef long long int ll; 19 typedef unsigned long long int ull; 20 typedef double db; 21 22 using namespace std; 23 24 inline int getint() 25 { 26 int res=0; 27 char c=getchar(); 28 bool mi=false; 29 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 30 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 31 return mi ? -res : res; 32 } 33 inline ll getll() 34 { 35 ll res=0; 36 char c=getchar(); 37 bool mi=false; 38 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 39 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 40 return mi ? -res : res; 41 } 42 43 //============================================================================== 44 //============================================================================== 45 //============================================================================== 46 //============================================================================== 47 48 49 struct edge 50 { 51 int in; 52 edge*nxt; 53 }pool[20050]; 54 edge*et; 55 edge*eds[10050]; 56 void addedge(int a,int b) 57 { et->in=b; et->nxt=eds[a]; eds[a]=et++; } 58 #define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt) 59 60 61 int n,m; 62 63 int dep[10050]; 64 int deg[10050]; 65 bool used[10050]; 66 67 68 int main() 69 { 70 while(scanf("%d%d",&n,&m)>0) 71 { 72 et=pool; 73 memset(eds,0,sizeof(edge*)*(n+1)); 74 memset(dep,0,sizeof(int)*(n+1)); 75 memset(deg,0,sizeof(int)*(n+1)); 76 memset(used,0,sizeof(bool)*(n+1)); 77 78 for(int i=0;i

q; 87 for(int i=0;i

in]--; 97 if(deg[e->in]==0) 98 { 99 dep[e->in]=dep[x]+1;100 q.push(e->in);101 }102 }103 }104 105 bool ok=true;106 for(int i=0;i

View Code

HDU 1811

判断是否存在拓扑序,以及是否存在确定的拓扑序.

判断是否存在,就是按照上面的,能把所有点压入队列就肯定存在可行拓扑序列.

(一般有环就说明限制条件存在矛盾,这个环中的任意一个节点都不能被压入队列)

拓扑序列只有一个的条件是每时每刻队列中仅有一个节点.(否则这两个节点的顺序不定.)

处理那个等号非常麻烦.三次提交都错在那里. 这个题看起来还可以用差分约束.

1 #include 
      
         2 #include 
       
          3 #include 
        
           4    5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 10 #include 
             
               11 #include 
              
                12 #include 
                13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 17 typedef unsigned int uint; 18 typedef long long int ll; 19 typedef unsigned long long int ull; 20 typedef double db; 21 22 using namespace std; 23 24 inline int getint() 25 { 26 int res=0; 27 char c=getchar(); 28 bool mi=false; 29 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 30 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 31 return mi ? -res : res; 32 } 33 inline ll getll() 34 { 35 ll res=0; 36 char c=getchar(); 37 bool mi=false; 38 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 39 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 40 return mi ? -res : res; 41 } 42 43 //============================================================================== 44 //============================================================================== 45 //============================================================================== 46 //============================================================================== 47 48 struct edge 49 { 50 int in; 51 edge*nxt; 52 }pool[20050]; 53 edge*et; 54 edge*eds[2][10050]; 55 void addedge(int i,int j,int k) 56 { et->in=j; et->nxt=eds[k][i]; eds[k][i]=et++; } 57 #define FOREACH_EDGE(i,j,f) for(edge*i=eds[f][j];i;i=i->nxt) 58 59 //union find 60 int f[10050]; 61 void INIT(int size) 62 { for(int i=0;i
                   
                    0) 82 { 83 INIT(n+1); 84 memset(eds[1],0,sizeof(edge*)*(n+1)); 85 memset(block,0xFF,sizeof(int)*(n+1)); 86 et=pool; 87 btot=0; 88 89 bool unc=false; 90 bool conf=false; 91 92 for(int i=0;i
                    
                     ') addedge(A[i],B[i],1);104 else if(C[i]=='<') addedge(B[i],A[i],1);105 }106 107 if(conf) { printf("CONFLICT\n"); continue; }108 109 for(int i=0;i
                     
                      in])123 {124 addedge(block[i],block[e->in],0);125 deg[block[e->in]]++;126 }127 128 queue
                      
                        q;129 for(int i=0;i
                       
                        1) unc=true;135 int x=q.front(); q.pop();136 used[x]=true;137 FOREACH_EDGE(e,x,0)138 {139 deg[e->in]--;140 if(deg[e->in]==0)141 q.push(e->in);142 }143 }144 145 for(int i=0;i

View Code

POJ 3287

裸的拓扑标号. 要求优先级.

做的时候,把边反向,做拓扑排序,然后逆序标号.

千万想清楚程序在干什么! 这道题是 "对标号进行限制" 以及 "对每个标号进行赋权" 然后 "输出标号的权值".

1 #include 
      
         2 #include 
       
          3 #include 
        
           4    5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 10 #include 
             
               11 #include 
              
                12 #include 
                13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 17 typedef unsigned int uint; 18 typedef long long int ll; 19 typedef unsigned long long int ull; 20 typedef double db; 21 22 using namespace std; 23 24 inline int getint() 25 { 26 int res=0; 27 char c=getchar(); 28 bool mi=false; 29 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 30 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 31 return mi ? -res : res; 32 } 33 inline ll getll() 34 { 35 ll res=0; 36 char c=getchar(); 37 bool mi=false; 38 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 39 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 40 return mi ? -res : res; 41 } 42 43 db eps=1e-20; 44 inline bool feq(db a,db b) 45 { return fabs(a-b)
                   
                     48 inline Type avg(const Type a,const Type b) 49 { return a+((b-a)/2); } 50 51 //========================================================== 52 //========================================================== 53 //========================================================== 54 //========================================================== 55 56 57 struct edge 58 { 59 int in; 60 edge*nxt; 61 }pool[40050]; 62 edge*et=pool; 63 edge*eds[205]; 64 void addedge(int a,int b) 65 { et->in=b; et->nxt=eds[a]; eds[a]=et++; } 66 #define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt) 67 68 69 int n,m; 70 int deg[205]; 71 int label[205]; 72 73 int main() 74 { 75 int T=getint(); 76 while(T--) 77 { 78 n=getint(); 79 m=getint(); 80 81 memset(eds,0,sizeof(edge*)*(n+1)); 82 memset(deg,0,sizeof(int)*(n+1)); 83 memset(label,0,sizeof(int)*(n+1)); 84 et=pool; 85 86 int tot=0; 87 88 for(int i=0;i

q; 97 for(int i=0;i

in]--;107 if(deg[e->in]==0)108 q.push(e->in);109 }110 }111 112 if(tot!=n) printf("-1\n");113 else114 {115 printf("%d",label[0]);116 for(int i=1;i

View Code

POJ 1270

枚举拓扑序并输出.

首先读入比较坑.....WA掉一次的原因是没排序...题目要求不是按照读入的字典序而是字母字典序.....果断写了个冒泡上去......然后就A了.....

这个算是拓扑排序么?唉随便吧....

1 #include 
      
         2 #include 
       
          3 #include 
        
           4    5 #include 
         
            6 #include 
          
             7 #include 
           
             8 #include 
            
              9 10 #include 
             
               11 #include 
              
                12 #include 
                13 #include 
                
                  14 #include 
                 
                   15 #include 
                  
                    16 17 typedef unsigned int uint; 18 typedef long long int ll; 19 typedef unsigned long long int ull; 20 typedef double db; 21 22 using namespace std; 23 24 inline int getint() 25 { 26 int res=0; 27 char c=getchar(); 28 bool mi=false; 29 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 30 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 31 return mi ? -res : res; 32 } 33 inline ll getll() 34 { 35 ll res=0; 36 char c=getchar(); 37 bool mi=false; 38 while(c<'0' || c>'9') mi=(c=='-'),c=getchar(); 39 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar(); 40 return mi ? -res : res; 41 } 42 43 //========================================================== 44 //========================================================== 45 //========================================================== 46 //========================================================== 47 48 49 struct edge 50 { 51 int in; 52 edge*nxt; 53 }pool[40050]; 54 edge*et=pool; 55 edge*eds[205]; 56 void addedge(int a,int b) 57 { et->in=b; et->nxt=eds[a]; eds[a]=et++; } 58 #define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt) 59 60 int n,m; 61 62 char inp1[105]; 63 int pos[256]; 64 char inp2[1050]; 65 66 int deg[105]; 67 68 int cur[105]; 69 bool ins[105]; 70 void DFS(int dep) 71 { 72 if(dep==n) 73 { 74 for(int i=0;i
                   
                    in]--; 85 DFS(dep+1); 86 FOREACH_EDGE(e,i) deg[e->in]++; 87 ins[i]=false; 88 } 89 } 90 91 int main() 92 { 93 while(true) 94 { 95 gets(inp1); 96 if(feof(stdin)) break; 97 gets(inp2); 98 99 {100 n=0;101 int p=0; 102 while(inp1[p]!=0)103 {104 if('a'<=inp1[p] && inp1[p]<='z') 105 pos[inp1[p]]=n,inp1[n++]=inp1[p];106 p++;107 }108 109 for(int i=0;i
                    
                     inp1[j])112 swap(inp1[i],inp1[j]),swap(pos[inp1[i]],pos[inp1[j]]);113 114 }115 116 et=pool;117 memset(eds,0,sizeof(int)*(n+1));118 memset(deg,0,sizeof(int)*(n+1));119 120 {121 int p=0;122 int c=0;123 char a;124 while(inp2[p]!=0)125 {126 if('a'<=inp2[p] && inp2[p]<='z')127 {128 if(c==1)129 {130 addedge(pos[a],pos[inp2[p]]);131 deg[pos[inp2[p]]]++;132 c=0;133 }134 else a=inp2[p],c++;135 }136 137 p++;138 }139 }140 141 DFS(0);142 143 printf("\n");144 }145 146 return 0;147 }

View Code

转载于:https://www.cnblogs.com/DragoonKiller/p/4451821.html