hdu2121 Ice_cream’s world II 最小树形图（难）

　　这题比HDU4009要难一些。做了4009,大概知道了最小树形图的解法。拿到这题，最直接的想法是暴力。n个点试过去，每个都拿来做一次根。最后WA了，估计是超时了。（很多题都是TLE说成WA，用了G++才知道是TLE,不断修改代码也看不出来错哪了）。

　　网上的正解是添加一个虚拟根（树根），使得它与n个点都有边相连。HDU4009题这样得到的边有实际的意义，好理解。这题这样得到的边不好理解，并且边权应该是多少也有讲究。别人的解题报告中是把这些边的权值设为原本所有边的权值之和加1。这样做的目的，是为了完全把这些边与原本的边区分开。最后得到的最小树形图有且仅有一条这样的边，并且这条边的终点就是所求的设立首都的点。从这里就可以看出边权设置的作用了。

　　从4009和2121这两题来看，解无根的最小树形图问题的套路是：添加一个虚根，虚根与其他n个点要连边。其中比较重要的巧妙地使这些的权值有意义。这样就是“无根”转换为“有根”。然后就可以用模版了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N = , M=,INF=0x3f3f3f3f;

 int pre[N],id[N],in[N],vis[N];

 int tot, Minr;//边数

 struct node

 {

     int u,v,w;

 }e[M];

 void adde(int i,int j,int k)

 {

     e[tot].u=i;e[tot].v=j;e[tot++].w=k;

 }

 long long  zhuliu(int root ,int vn)

 {

     long long  ans=;

     int cnt;

     while()

     {

         for(int i=;i<vn;i++)

             in[i]=INF,id[i]=-,vis[i]=-;

         for(int i=;i<tot;i++)

         {

             if(in[e[i].v]>e[i].w && e[i].u!=e[i].v)

             {

                 pre[e[i].v]=e[i].u;

                 if(e[i].u==root) Minr=i;

                 in[e[i].v]=e[i].w;

             }

         }

         in[root]=;

         pre[root]=root;

         for(int i=;i<vn;i++)

         {

             ans+=in[i];

             if(in[i]==INF)

                 return -;

         }

         cnt=;

         for(int i=;i<vn;i++)

         {

             if(vis[i]==-)

             {

                 int t=i;

                 while(vis[t]==-)

                 {

                     vis[t]=i;

                     t=pre[t];

                 }

                 if(vis[t]!=i || t==root) continue;

                 for(int j=pre[t];j!=t;j=pre[j])

                     id[j]=cnt;

                 id[t]=cnt++;

             }

         }

         if(cnt==) break;

         for(int i=;i<vn;i++)

             if(id[i]==-)

                 id[i]=cnt++;

         for(int i=;i<tot;i++)

         {

             int u,v;

             u=e[i].u;

             v=e[i].v;

             e[i].u=id[u];

             e[i].v=id[v];

             e[i].w-=in[v];

         }

         vn=cnt;

         root=id[root];

     }

     return ans;

 }

 int main()

 {

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

     int n,m,i,j,a,b,c,sum;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         tot=;

         sum=;

         for(i=;i<m;i++)

         {

             scanf("%d%d%d",&a,&b,&c);

             adde(a,b,c);

             sum+=c;

         }

         sum++;

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

         {

             adde(n,i,sum);

         }

         a=zhuliu(n,n+);

         Minr-=m;

         if(a==-||a>=*sum) printf("impossible\n");

         else printf("%d %d\n",a-sum,Minr);

         printf("\n");

     }

     return ;

 }

巴特西

hdu2121 Ice_cream’s world II 最小树形图（难）

最新文章

热门文章