模板题 . UVA--- 11183传送
还有这道 POJ 3164 点这传送
举个例子：某个图的部分图中， 1->2权值为3， 2->1权值为4， 3->1权值为9， 4->2权值为7。 那么可以看到，结点1和结点2是形成了一个环的。我们仅从其大小不知道删除哪条边比较好，这时看到3->1权值为9， 如果走这条边，那么接下来只能删除掉2->1这条边，同理走4->2的话就要删除掉1->2这条边。 那么就不妨建立新图， 将1和2缩成一点，3->1的权值就变成了9-4=5， 4->2的权值变成了7-3=4。 这样的话，就相当于变相删除了不需要走的边了。形成新图后，又变成了最小树形图的求解，就这样循环下去，直到图中的最小边集没有环为止.
裸模板,直接上:
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#define ll long long int
#define db double
using namespace std;
const int maxn=1e3; //点数[0-n-1]
const int maxm=1e7; //边数
const int inf=1e9;
int n,m;
struct edge
{
int u,v,w;
} s[maxn*maxn/2];
int pre[maxn]; //记录前驱.
int id[maxn];
int vis[maxn];
int in[maxn];
void p(int *a,int n)
{
for(int i=1;i<=n;i++)
printf("%d%c",a[i],i==n?'\n':' ');
}
int dirMst(int root) //这种图中根一定是确定的.
{
int ans=0;
while(1)
{
for(int i=0; i<n; i++)
in[i]=inf;
memset(id,-1,sizeof(id));
memset(vis,-1,sizeof(vis));
for(int i=0;i<m;i++)
{
int u=s[i].u;
int v=s[i].v;
int w=s[i].w;
if(w<in[v] && v != u )
{
pre[v] = u;
in[v] = w;
}
} //求最小入边集
in[root]=0;
pre[root]=root;//为之后的遍历做准备，in[]用于存储最小边集
for(int i=0; i<n; i++)
{
if(in[i] == inf)
return -1;
ans += in[i];
} //此循环判断是否有孤立节点，同时计算当前最小权值和
int idx = 0;//idx是用来给新的节点赋名称的（新序号）
for(int i=0;i<n;i++)
{
if(vis[i] == -1 )
{
int u = i;
while(vis[u] == -1){
vis[u] = i;
u = pre[u];
} //将vis[u]赋值为i是为了做标记
if(vis[u] != i || u == root ) continue; //判断是否形成环,未形成环就直接跳出.
//只有是环的才能进入for循环.
for(int v=pre[u];v!=u;v=pre[v] )
id[v] = idx; //给环上的点赋值一个统一的标号，形成一个新的点(id[i]用于存储i点的新标号）
id[u] = idx++; //不在环上的新标号跟着另.
}
}
if(idx==0) break;//没有环，跳出循环
for(int i=0;i<n;i++){
if(id[i]== -1){
id[i]=idx++;//在上一个循环给环赋予新的序号，这一步是给非环的点新的序号，保证新图中每个点有相应的标号
}
}
for(int i=0;i<m;i++) //造新图.
{
s[i].w -= in[s[i].v];//把每个点的其他入边看做环的入边，将增值赋给环的入边，作为新图的这个新的点的该条入边的权值
s[i].u = id[s[i].u];
s[i].v = id[s[i].v];
} //这个循环是修改旧图，把id中存储的映射到图中形成新图
n = idx; //这个很重要，要知道把环捏成一个点，那么图中点个数改变了，所以循环次数改变
root = id[root];//给根新的标号
}
return ans;
}
int main()
{
int t;
cin >> t;
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0; i<m; i++)
{
scanf("%d%d%d",&s[i].u,&s[i].v,&s[i].w);
}
int res=dirMst(0); //以0为根开始搜.
printf("%d\n",res);
}
}
