题目地址：HDU 2121 这题没有给定根。最容易想到的当然是暴力，枚举所有的根，，但是TLE是显然的。。为了处理不定根的情况，可以虚拟一个根，然后用这个根去跟所有的点连边，权值为其他所有权值的和+1，目的是防止成为最小树形图的一条边。然后跑出最小树形图后，那么这个虚拟根肯定跟一个实际根相连，这时候根就找到了，然后再在最终的总花费中减去虚拟的那条边的权值就可以了。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=40000+10;int cnt, n, Minroot;int in[1100], id[1100], color[1100], pre[1100];struct node{int u, v, w;}edge[20000];void add(int u, int v, int w){edge[cnt].u=u;edge[cnt].v=v;edge[cnt++].w=w;}int d_mst(int root){int ans=0, i, u, v;while(1){memset(in,INF,sizeof(in));for(i=0;i<cnt;i++){u=edge[i].u;v=edge[i].v;if(u!=v&&edge[i].w<in[v]){in[v]=edge[i].w;if(u==root) Minroot=i;pre[v]=u;}}for(i=0;i<n;i++){if(i!=root&&in[i]==INF) return -1;}int tot=0;memset(color,-1,sizeof(color));memset(id,-1,sizeof(id));in[root]=0;for(i=0;i<n;i++){ans+=in[i];u=i;while(color[u]!=i&&id[u]==-1&&u!=root){color[u]=i;u=pre[u];}if(id[u]==-1&&u!=root){for(v=pre[u];v!=u;v=pre[v]){id[v]=tot;}id[u]=tot++;}}if(!tot) break;for(i=0;i<n;i++){if(id[i]==-1) id[i]=tot++;}for(i=0;i<cnt;i++){v=edge[i].v;edge[i].u=id[edge[i].u];edge[i].v=id[edge[i].v];if(edge[i].u!=edge[i].v){edge[i].w-=in[v];}}n=tot;root=id[root];}return ans;}int main(){int m, i, u, v, w, ans, x, sum;while(scanf(“%d%d”,&n,&m)!=EOF){cnt=0;x=m;sum=0;while(m–){scanf(“%d%d%d”,&u,&v,&w);add(u,v,w);sum+=w;}sum++;for(i=0;i<n;i++){add(n,i,sum);}n++;ans=d_mst(n-1);if(ans==-1||ans>=2*sum) puts(“impossible\n”);else printf(“%d %d\n\n”,ans-sum,Minroot-x);}return 0;}
要铭记在心;每天都是一年中最美好的日子
