hdoj 继续畅通工程 Kruskal算法实现最小生成树

#include<iostream>
#include<algorithm>
using namespace std;
int par[10005],ran[10005];
int u[10005],v[10005],w[10005],r[10005],k[10005];
int cmp(const int i,const int j)//间接排序函数，按边权值从小到大排
    {return w[i]<w[j];}
void inital(int n)
{
    for(int i=1;i<=n;i++)
    {
        par[i]=i;
        ran[i]=0;
    }
}
int find(int x)
{
    if(x==par[x])return x;
    else return par[x]=find(par[x]);
}
void unite(int x,int y)
{
    int a=find(x);
    int b=find(y);
    if(a==b)return ;
    if(ran[a]<ran[b])par[a]=b;
    else
    {
        par[b]=a;
        if(ran[a]==ran[b])
        ran[a]++;
    }
}
int kruskal(int n,int m)
{
	int ans=0;
	inital(n);
	for(int i=0;i<m;i++)
		r[i]=i;
	sort(r,r+m,cmp);//这个排序要注意数组的范围，不然会wa到死
	for(int i=0;i<m;i++)
	{
		int e=r[i];
		int x=find(u[e]);
		int y=find(v[e]);
		if(x!=y)//判圈，如果不在同一个连通分量，即根不同，加入不会产生圈，如果根相同，则不加入
		{
			ans+=w[e];
			unite(v[e],u[e]);
		}
	}
	return ans;
}
int main()
{
	int i,j,m,n;
	while(cin>>n&&n)
	{
		m=(n-1)*n/2;
		for(i=0;i<m;i++)
		{
		    cin>>u[i]>>v[i]>>w[i]>>k[i];
			if(k[i]==1)w[i]=0;
		}
		cout<<kruskal(n,m)<<endl;
	}
}#include<iostream>
#include<algorithm>
using na