kuangbin专题八 UVA11183 Teen Girl Squad（最小树形图）

本文主要是介绍kuangbin专题八 UVA11183 Teen Girl Squad（最小树形图），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
给你N个点，编号为0到N-1，M条边的信息，边为单向边，问联通所有点的最小代价是多少。
题解：
最小树形图模板上，上代码就行了。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int MAXN=1000+7;
struct node
{int u,v,w;
}map[40000+7];
int pre[MAXN];
int ID[MAXN];
int vis[MAXN];
int IN[MAXN];
int n,m;
int zhuliu_mst(int root,int V,int E)
{int sum=0;while(true){//1.找最小入边for(int i=0;i<V;i++) IN[i]=INF;for(int i=0;i<E;i++){int u=map[i].u;int v=map[i].v;if(map[i].w<IN[v]&&u!=v){pre[v]=u;IN[v]=map[i].w;}}for(int i=0;i<V;i++){if(i==root) continue;if(IN[i]==INF) return -1;} //2.找环int cnt=0;memset(ID,-1,sizeof(ID));memset(vis,-1,sizeof(vis));IN[root]=0;for(int i=0;i<V;i++)//标记每个环 {sum+=IN[i];int 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]=cnt;}ID[v]=cnt++;}}if(cnt==0) break;//无环 for(int i=0;i<V;i++){if(ID[i]==-1)ID[i]=cnt++;}//3.缩点,重新标记for(int i=0;i<E;i++){int u=map[i].u;int v=map[i].v;map[i].u=ID[u];map[i].v=ID[v];if(ID[u]!=ID[v]){map[i].w-=IN[v];}} V=cnt;root=ID[root];}return sum;
}
int main()
{int t,k=1;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(int i=0;i<m;i++){scanf("%d%d%d",&map[i].u,&map[i].v,&map[i].w);if(map[i].u==map[i].v)map[i].w=INF;}int ans=zhuliu_mst(0,n,m);printf("Case #%d: ",k++);if(ans==-1)printf("Possums!\n");elseprintf("%d\n",ans);}
}