HDUOJ 2121 Ice_cream’s world II（不定根的最小树形图－好题）

题目连接～～～

　　本题是求不定根的情况，如果以每个点为根来一次最小树形图，那必定超时。这里我们可以虚拟出来一个点作为根，然后，让这个点连接所有顶点，那边的权值是多少呢？就是所有权值和加１，这样保证了如果最小树形图存在，那么只有一条虚拟的边加入到最小树形图中，让总和减去它就可以了，还有一种情况就是如果原先图不存在最小树形图，那么有可能选择两条虚拟边加入最小树形图，只要判断一下，最后的值是否大于等于原先权值和加１的二倍，是则无解，否则存在最小树形图。那怎么求最小树形图在原先图中的根节点呢？通过上面我们知道，最后只有一个虚拟边x加入最小树形图，而这个边是加给第x-m点的边，所以在图不断变化的过程中只要记住虚拟边的边号x，然后x-m就是答案。

代码：

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <cstdio>
     
    
   

    

     

    
    

     

      #include <cstring>
     
    
   

    

     

    
    

     

      #include <cstdlib>
     
    
   

    

     

    
    

     

      #include <cmath>
     
    
   

    

     

    
    

     

      #include <ctime>
     
    
   

    

     

    
    

     

      #include <algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define INF 0x3f3f3f3f
     
    
   

    

     

    
    

     

      const double esp = 0.00000001 ;
     
    
   

    

     

    
    

     

      const int MX = 20000 + 10 ;
     
    
   

    

     

    
    

     

      const int MY = 1e3 + 10 ;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int tot ,f_num ;
     
    
   

    

     

    
    

     

      typedef struct {
     
    
   

    

     

    
    

     
 int u ,v ,w ;
     
    
   

    

     

    
    

     
 int next ;
     
    
   

    

     

    
    

     

      }Edge ;
     
    
   

    

     

    
    

     

      Edge E[MX] ;
     
    
   

    

     

    
    

     

      int head[MY] ,In[MY] ,pre[MY] ,Id[MY] ,vis[MY] ;
     
    
   

    

     

    
    

     

      void Add_edge(int u ,int v ,int w){
     
    
   

    

     

    
    

     

       E[tot].u = u ; E[tot].v = v ; E[tot].w = w ; E[tot].next = head[u] ; head[u] = tot++ ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int Zhuliu(int root ,int n ,int m ,Edge E[]){
     
    
   

    

     

    
    

     
 int u ,v ,w ,ret = 0 ;
     
    
   

    

     

    
    

     
 while(1){
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < n ; ++i)
     
    
   

    

     

    
    

     

       In[i] = INF ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < m ; ++i){
     
    
   

    

     

    
    

     

       u = E[i].u ; v = E[i].v ; w = E[i].w ;
     
    
   

    

     

    
    

     
 if(u != v && w < In[v]){
     
    
   

    

     

    
    

     

       In[v] = w ;
     
    
   

    

     

    
    

     

       pre[v] = u ;
     
    
   

    

     

    
    

     
 if(u == root) f_num = i ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < n ; ++i){
     
    
   

    

     

    
    

     
 if(i != root && In[i] == INF)
     
    
   

    

     

    
    

     
 return -1 ;//有孤立的点，没有解
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int nt = 0 ;
     
    
   

    

     

    
    

     
 memset(Id ,-1 ,sizeof(Id)) ;
     
    
   

    

     

    
    

     
 memset(vis ,-1 ,sizeof(vis)) ;
     
    
   

    

     

    
    

     

       In[root] = 0 ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < n ; ++i){
     
    
   

    

     

    
    

     

       ret += In[i] ;
     
    
   

    

     

    
    

     

       v = i ;
     
    
   

    

     

    
    

     
 while(vis[v] != i && Id[v] == -1 && v != root){
     
    
   

    

     

    
    

     

       vis[v] = i ;
     
    
   

    

     

    
    

     

       v = pre[v] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(v != root && Id[v] == -1){
     
    
   

    

     

    
    

     
 for(int u = pre[v] ; u != v ; u = pre[u])
     
    
   

    

     

    
    

     

       Id[u] = nt ;
     
    
   

    

     

    
    

     

       Id[v] = nt++ ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(nt == 0) break ;//没有有向环
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < n ; ++i)
     
    
   

    

     

    
    

     
 if(Id[i] == -1)
     
    
   

    

     

    
    

     

       Id[i] = nt++ ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < m ; ++i){
     
    
   

    

     

    
    

     

       v = E[i].v ;
     
    
   

    

     

    
    

     

       E[i].u = Id[E[i].u] ;
     
    
   

    

     

    
    

     

       E[i].v = Id[E[i].v] ;
     
    
   

    

     

    
    

     
 if(E[i].u != E[i].v)
     
    
   

    

     

    
    

     

       E[i].w -= In[v] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       n = nt ;
     
    
   

    

     

    
    

     

       root = Id[root] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return ret ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
 //freopen("input.txt" ,"r" ,stdin) ;
     
    
   

    

     

    
    

     
 int n , m ;
     
    
   

    

     

    
    

     
 while(~scanf("%d%d" ,&n ,&m)){
     
    
   

    

     

    
    

     

       tot = 0 ; f_num = 0 ;
     
    
   

    

     

    
    

     
 int sum = 1 ,u ,v ,w ;
     
    
   

    

     

    
    

     
 memset(head ,-1 ,sizeof(head)) ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < m ; ++i){
     
    
   

    

     

    
    

     
 scanf("%d%d%d" ,&u ,&v ,&w) ;
     
    
   

    

     

    
    

     
 if(u != v){
     
    
   

    

     

    
    

     

       Add_edge(u ,v ,w) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       sum += w ;//把所有的权值都加起来
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < n ; ++i){//再加上n条边
     
    
   

    

     

    
    

     

       Add_edge(n ,i ,sum) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int ans = Zhuliu(n ,n+1 ,n+m ,E) ;
     
    
   

    

     

    
    

     
 if(ans == -1 || ans >= sum*2) printf("impossible\n") ;
     
    
   

    

     

    
    

     
 else printf("%d %d\n" ,ans-sum ,f_num - m) ;
     
    
   

    

     

    
    

     
 puts("") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/52054167