首页 > 代码库 > hdu2121 Ice_cream’s world II 最小树形图（难）
hdu2121 Ice_cream’s world II 最小树形图（难）
这题比HDU4009要难一些。做了4009,大概知道了最小树形图的解法。拿到这题，最直接的想法是暴力。n个点试过去，每个都拿来做一次根。最后WA了，估计是超时了。（很多题都是TLE说WA，不断修改代码也看不出来错哪了）。
网上的正解是添加一个虚拟根（树根），使得它与n个点都有边相连。HDU4009题这样得到的边有实际的意义，好理解。这题这样得到的边不好理解，并且边权应该是多少也有讲究。别人的解题报告中是把这些边的权值设为原本所有边的权值之和加1。这样做的目的，是为了完全把这些边与原本的边区分开。最后得到的最小树形图有且仅有一条这样的边，并且这条边的终点就是所求的设立首都的点。从这里就可以看出边权设置的作用了。
从4009和2121这两题来看，解无根的最小树形图问题的套路是：添加一个虚根，虚根与其他n个点要连边。其中比较重要的巧妙地使这些的权值有意义。这样就是“无根”转换为“有根”。然后就可以用模版了。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N = 1010, M=10005,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=0; int cnt; while(1) { for(int i=0;i<vn;i++) in[i]=INF,id[i]=-1,vis[i]=-1; for(int i=0;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]=0; pre[root]=root; for(int i=0;i<vn;i++) { ans+=in[i]; if(in[i]==INF) return -1; } cnt=0; for(int i=0;i<vn;i++) { if(vis[i]==-1) { int t=i; while(vis[t]==-1) { 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==0) break; for(int i=0;i<vn;i++) if(id[i]==-1) id[i]=cnt++; for(int i=0;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=0; sum=0; for(i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); adde(a,b,c); sum+=c; } sum++; for(i=0;i<n;i++) { adde(n,i,sum); } a=zhuliu(n,n+1); Minr-=m; if(a==-1||a>=2*sum) printf("impossible\n"); else printf("%d %d\n",a-sum,Minr); printf("\n"); } return 0;}
hdu2121 Ice_cream’s world II 最小树形图（难）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。