C++——NOIP模拟题——保留道路

很久很久以前有一个国家，这个国家有 N 个城市，城市由 1，2，3，…，,N 标号，城市间有 M 条双向道路，每条道路都有两个属性 g 和 s ，两个城市间可能有多条道路，并且可能存在将某一城市与其自身连接起来的道路。后来由于战争的原因，国王不得不下令减小花费从而关闭一些道路，但是必须要保证任意两个城市相互可达。

道路花费的计算公式为 wG*max{所有剩下道路的属性g}+wS*max{所有剩下道路的属性s}，其中 wG 和 wS 是给定的值。国王想要在满足连通性的前提下使这个花费最小，现在需要你计算出这个花费。

第一行包含两个正整数 N 和 M 。
第二行包含两个正整数 wG 和 wS 。
后面的 M 行每行描述一条道路，包含四个正整数 u，v，g，s，分别表示道路连接的两个城市以及道路的两个属性。

输出一个整数，表示最小花费。若无论如何不能满足连通性，输出 -1 。

输入

3 3 
2 1 
1 2 10 15 
1 2 4 20 
1 3 5 1

输出

30

【数据规模与约定】
对于 10% 的数据，N≤10；M≤20；
对于 30% 的数据，N≤100；M≤1000；
对于 50% 的数据，N≤200；M≤5000；
对于 100% 的数据，N≤400；M≤50000；wG,wS,g,s≤1000000000。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
long long wg,wss;
struct node{
	int u,v,g,s;
}a[50001];
long long ans=1e18;
int f[401],s[401],top;
inline int cmp(const void *a,const void *b)
{
	return (*(struct node *)a).g-(*(struct node *)b).g;
}
inline int find(int x)
{
	if(!f[x]) return x;
	return f[x]=find(f[x]);
}
int main()
{
	scanf("%d%d%l64d%l64d",&n,&m,&wg,&wss);
	int i,j,num,u,v;
	for(i=1;i<=m;++i) scanf("%d%d%d%d",&a[i].u,&a[i].v,&a[i].g,&a[i].s);
	qsort(a+1,m,sizeof(a[0]),cmp);
	for(i=1;i<=m;++i)
	{
		for(j=1;j<=n;++j) f[j]=0;
		for(j=top;j>=1;--j)
			if(a[s[j]].s>a[i].s) s[j+1]=s[j];
			else break;
		++top;
		s[j+1]=i;
		num=0;
		for(j=1;j<=top;++j)
		{
			u=find(a[s[j]].u);
			v=find(a[s[j]].v);
			if(u!=v)
			{
				f[u]=v;
				s[++num]=s[j];
			}
		}
		if(num+1==n) ans=min(ans,wg*a[i].g+wss*a[s[num]].s);
		top=num;
	}
	if(ans==1<<30) puts("-1");
	else cout<<ans<<endl;
	return 0;
}