继续畅通工程

解题思路:最小生成树,如果道路是好的就提前连上且不用成本

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
int f[1000];
struct node
{
	int from;
	int to;
	int w;
};
int find(int x)
{
	if(x!=f[x])
	{
		return f[x]=find(f[x]);
	}
	return x;
}
long long ans=0;
void meare(node a,bool t)
{
	int x=find(a.from);
	int y=find(a.to);
	if(x!=y)
	{
		f[y]=x;
		if(t)ans+=a.w;
		
	}
}
vector<node>v;
bool cmp(node a,node b)
{
	return a.w<b.w;
}
int main()
{
	int n;
	while(cin>>n&&n)
	{
		ans=0;
		for(int i=0;i<=n;i++)
		{
			f[i]=i;
		}
		for(int i=1;i<=(n*(n-1)/2);i++)
		{
			int d;
			node a;
			cin>>a.from>>a.to>>a.w>>d;
			if(d==1)
			{
				meare(a,0);
			}
			else
			{
				v.push_back(a);
			}
		}
		sort(v.begin(),v.end(),cmp);
		for(int i=0;i<v.size();i++)
		{
			meare(v[i],1);
		}
		v.clear();
		cout<<ans<<endl;	
	}
	return 0;
}