问题描述：

1001 Battle Over Cities - Hard Version （35 分）

It is vitally important to have all the cities connected by highways in a war. If a city is conquered by the enemy, all the highways from/toward that city will be closed. To keep the rest of the cities connected, we must repair some highways with the minimum cost. On the other hand, if losing a city will cost us too much to rebuild the connection, we must pay more attention to that city.

Given the map of cities which have all the destroyed and remaining highways marked, you are supposed to point out the city to which we must pay the most attention.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 2 numbers N (≤500), and M, which are the total number of cities, and the number of highways, respectively. Then M lines follow, each describes a highway by 4 integers: City1 City2 Cost Status where City1 and City2 are the numbers of the cities the highway connects (the cities are numbered from 1 to N), Cost is the effort taken to repair that highway if necessary, and Status is either 0, meaning that highway is destroyed, or 1, meaning that highway is in use.

Note: It is guaranteed that the whole country was connected before the war.

Output Specification:

For each test case, just print in a line the city we must protest the most, that is, it will take us the maximum effort to rebuild the connection if that city is conquered by the enemy.

In case there is more than one city to be printed, output them in increasing order of the city numbers, separated by one space, but no extra space at the end of the line. In case there is no need to repair any highway at all, simply output 0.

Sample Input 1:

4 5
1 2 1 1
1 3 1 1
2 3 1 0
2 4 1 1
3 4 1 0

Sample Output 1:

1 2

Sample Input 2:

4 5
1 2 1 1
1 3 1 1
2 3 1 0
2 4 1 1
3 4 2 1

Sample Output 2:

0

 

这一题也是关于最小生成树的问题，同样利用并查集+Kruskal算法即可解决。。。

首先，对于所有读入的边，先按照Status排序，再按照Cost排序。然后，对于每个需要保卫的城市，遍历边的集合，对于不含此次城市的边，修改相应并查集的状态，若Status=0且边所连接的两个城市不在一个集合里，则当前城市的费用需要加上这条边的维修费用。最后，遍历每个城市的维修费用，输出相应的城市序号。

AC代码：

#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int c1,c2,ct,st;
	bool operator< (const edge& ee)const
	{
		if(st!=ee.st)
		return st>ee.st;
		else
		return ct<ee.ct;
	}
} e;
vector<int> vc;
inline int fr(int n)
{
	int rn=n;
	for(;vc[rn];rn=vc[rn]);
	if(rn-n)
	vc[n]=rn;
	return rn;
}
int main()
{
//	freopen("data.txt","r",stdin);
	int n,m,c=0,ci=0;
	scanf("%d %d",&n,&m);
	vector<edge> v;
	for(int i=0;i<m;i++)
	{
		scanf("%d %d %d %d",&e.c1,&e.c2,&e.ct,&e.st);
		v.emplace_back(e);
	}
	sort(v.begin(),v.end());
	vector<int> vr(n);
	for(int i=1;i<n+1;i++)
	{
		vc.clear();
		vc.resize(n+1,0);
		int cp=0;
		for(auto j:v)
		{
			if((j.c1-i)&&(j.c2-i))
			{
				int rc1=fr(j.c1);
				int rc2=fr(j.c2);
				if(rc1-rc2)
				{
					vc[max(rc1,rc2)]=min(rc1,rc2);
					if(!j.st) cp+=j.ct;
				}
			}
		}
		
		int flag=0;
		for(int j=1;j<n+1;j++)
		if(j-i && !vc[j]) flag++;
		if(flag-1) cp=10000;
		vr[i-1]=cp;
		if(cp>c)
		{
			c=cp;
			ci=i-1;
		}
	}
	if(c)
	{
		printf("%d",ci+1);
		for(int i=ci+1;i<n;i++)
		{
			if(vr[i]==c)
			printf(" %d",i+1);
		}
	}
	else
	printf("0");
	return 0;
}