无固定根节点的最小树形图,添加一个人工根节点,人工根节点到每个节点的权值sum>(所有边权值之和),
求出结果减去sum,只有人工根节点跟一个节点相连时才会有解,如果结果大于等于sum,则人工节点
跟多个节点相连,所以原图是不连通的,所以无解
#include<stdio.h> #include<string.h> #define inf 0x3fffffff #define M 10010 #define N 1010 int num,flag[N],id[N],ms[N],pre[N],ops; struct op { int u,v,w; }e[M]; int liuzhu(int root,int nm) { int sum=0; while(1) { for(int i=0;i<nm;i++) ms[i]=inf; memset(flag,-1,sizeof(flag)); memset(id,-1,sizeof(id)); for(i=0;i<num;i++)//除了根节点root以外的节点,选择一条权值最小的入边 { int u=e[i].u,v=e[i].v,w=e[i].w; if(w>=ms[v]||v==u)continue; ms[v]=w;pre[v]=u; if(u==root) ops=i;//如果该边起点是人工根节点,终点就是实际的根节点 } ms[root]=0; pre[root]=root; for(i=0;i<nm;i++) { if(ms[i]==inf)return -1;//如果有孤立点,则无解 sum+=ms[i]; } int res=0; for(i=0;i<nm;i++)//找有向环 { if(flag[i]==-1) { int u=i; while(flag[u]==-1) { flag[u]=i; u=pre[u]; } if(u==root||flag[u]!=i)continue;//环的起点不为root, for(int t=pre[u];t!=u;t=pre[t]) id[t]=res;//将环上的每个点用一个点代替 id[u]=res++; } } if(res==0) break; for(i=0;i<nm;i++) if(id[i]==-1)id[i]=res++;//将环外的点加进来 for(i=0;i<num;i++)//更新新图的相关值 { e[i].w-=ms[e[i].v];//应为ms[]已经加到sum了,所以减去 e[i].u=id[e[i].u]; e[i].v=id[e[i].v]; } nm=res;//新图节点的个数 root=id[root];//新图节点的根节点 } return sum; } int main() { int i,j,n,m,sum,cont; while(scanf("%d%d",&n,&m)!=EOF) { sum=0; for(i=0;i<m;i++) { scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); e[i].v++; e[i].u++; sum+=e[i].w; } sum+=1; for(i=0;i<n;i++)//加入人工节点0,到每个节点的权值为sum+1 { e[m+i].u=0; e[m+i].v=i+1; e[m+i].w=sum; } num=n+m; cont=liuzhu(0,n+1); if(cont==-1||cont-sum>=sum) printf("impossible\n"); else printf("%d %d\n",cont-sum,ops-m); printf("\n"); } return 0; }