自动搬运

查看原文

来自洛谷，原作者为

	VictorYuan 为什么要这样彼此争斗不休呢......

搬运于2025-08-24 22:04:10，当前版本为作者最后更新于2019-02-18 11:17:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本蒟蒻的第一篇题解。

写题解原因：（看题解的同学可以跳过）

我在考试的时候的一道题与这道题十分相似，场上写出了bug，晚上又调了一个半小时才通过。我想已经在这道题上用了三个小时了，不如写个题解，加深一下印象。

以下是正文

首先，通过读题，我们不难发现，问题可以转化成：一个N*M的无向图，我们需要删掉尽量多的权值较大边，使这张图依旧是联通的，求这些被删掉的边的权值之和。

我们知道，对于一个有n个点的图，我们最少需要n-1条边，把它们连成一个联通快，此时这张图是一个树。继续分析，因为我们要删掉尽量多的边，就是指剩下的边数最小;删掉权值较大的边，就是指要剩下的边权值较小。所以问题转化成：对于一个有n个点的无向图，我们需要连起来n-1条权值较小的边，使这时的边权值和最小。此时，我们只需把所有边权值之和再减去这个最小值，就是题目要求的最大值。而求这个最小值的过程，本质上就是最小生成树。所以本题就是一个求最小生成树的题。

但我们看数据范围：

N，M，P，Q都是十万以内，所以乘起来最多有一百亿个点！如果只用简单的最小生成树去做复杂度是吃不消了，所以我们需要更加深入地研究。

这里，我们以样例二为例，探索这道题的特殊性。

我们首先试图以所有边同时跑的Kruskal算法解决这道题。把所有边排序后，我们发现最短的边是一条横向边，连接某一行的2与3，那么这里我们可以判断，每一行的2和3这两个点，都会用到这一条边连接，因为这条边的权值最小，所以进行这样的操作，最后得到的答案一定是最优的，综上我们发现，对于一些边，我们只需要取一些代表表示，因为我们并不关心他的具体为止，所以这些代表可以看做是题目输入的边，这样我们就把边数压缩到了P+Q，这时我们再横纵跑两遍Kruskal就可以解决问题了。

但这道题还有一个细节。我们发现，如果一直按上面的做法，横向找出M-1条边，每条边使用N次，纵向找出N-1条边，每条边使用M次，最后共用 (M-1) * N + (N-1) * M = 2MN - M - N 条边，而实际上我们只需要 MN - 1 条边，二者之差为 MN - M - N + 1 ，很显然它们并不相同，所以我们还需要对本题进行进一步分析。

为了分析，首先，我们画出把上一步中的边连起来后的图形

排完序后，下一条边是一条纵向边，连接1与2，然后我们开始连边，但此时我们发现，我们不需要连M次，因为我们连到下图状态时，再向后连并不会起到把两棵树块合并到一起的作用，所以它没有连M次，而是M-1次。

同样的，我们继续进行，最小的边是横向边，连接1与2，我们也只需要连接N-1次可以了，下图就是最终的最小生成树。

那么我们现在需要解决的问题是，每一次找到一条边，判断出需要使用它几次。

还是从开始连边分析。不难发现：我们完全可以把每一个连通块看做一个点，于是上述过程就可以用下面的图表示。

第一步连边

下一步

最后

这样，最后只剩一个点，我们就把它合成了一个连通块。

分析：我们发现，如果之前没有连边，那么这一条边所代表的所有边都是需要连的，但我们在连了一条横边之后，在上图表示的信息为列数减一，即M-1，而因为M还表示一条纵边需要连的次数，所以，我们在求出一条纵边之后通过此时M的值可以知道它会连几条；同理，我们在连了一条纵边之后，相对应的N也会减一，对横边的影响也是如此。所以我们在跑Kruskal时要横纵同时跑，每次选边都更新一下M与N的值，这样跑到最后，我们就可算出这张图的最小生成树。

做法总结：我们需要挑出一行和一列做代表，选出在代表的行或列的所有边，本应横纵各跑一次最小生成树，但为了随时得到M与N的值，我们需要把横纵边放在一起跑最小生成树，这样我们就能得到全图的最小生成树，用所有边权之和减去这个最小生成树的权值和，就是最终答案。

如果还没有看懂，看看代码会加深一下理解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

struct node
{
	long long int x,y,z;//存放连的两个点和边长 
};
node a[100010],b[100010];//a数组存横边，b数组存纵边 
bool cmp(const node &ac,const node &wa)
{
	return ac.z<wa.z; 
}


long long int i,j,p,q,n,m,he=1,zo=1,fa,fb;
long long int faz[100010],fah[100010];
long long int ans=0,maxn=0;


long long int findz(long long int son)//横纵用两个并查集，因为我们需要横纵跑两个最小生成树 
{
	if(faz[son]==son) return son;
	faz[son]=findz(faz[son]);
	return faz[son];
}
long long int findh(long long int son)
{
	if(fah[son]==son) return son;
	fah[son]=findh(fah[son]);
	return fah[son];
}


int main()
{
	cin>>n>>m>>p>>q; 
	for(i=1;i<=p;i++)
	{
		scanf("%ld%ld%ld",&a[i].x,&a[i].y,&a[i].z);
		maxn+=a[i].z*n;//计算横边总权值 
	}
	for(i=1;i<=q;i++)
	{
		scanf("%ld%ld%ld",&b[i].x,&b[i].y,&b[i].z);
		maxn+=b[i].z*m;//计算纵边总权值
	}
	sort(a+1,a+p+1,cmp);//对横纵边分别从小到大排序 
	sort(b+1,b+q+1,cmp);
	
	
	
	
	for(i=0;i<=100001;i++)//初始并查集 
	{
		fah[i]=i;
		faz[i]=i;
	}
	
	
	while((m>1)&&(n>1))//注意这里的写法，只要横纵边有一个跑完了最小生成树，就退出循环 
	{
		if(a[he].z<b[zo].z)// 横纵边同时跑最小生成树，每次选出边权最小的判断是否加入加入其所在的树 
		{//横边较小的情况 
			fa=findh(a[he].x); fb=findh(a[he].y);
			if(fa!=fb)
			{
				fah[fa]=fb;
				--m;//减少纵边的需要数量 
				ans+=n*a[he].z;//最小生成树加上它的边权乘它的数量 
			}
			he++;
		}
		else 
		{//纵边较小的情况 
			fa=findz(b[zo].x); fb=findz(b[zo].y); 
			if(fa!=fb)
			{
				faz[fa]=fb;
				--n;//减小横边的需要数量 
				ans+=m*b[zo].z;//最小生成树加上它的边权乘它的数量 
			}
			zo++;
		}
	}
	
	
	while(m>1)//纵边已经连完，而横边还没连完，就继续连横边 
	{
		fa=findh(a[he].x); fb=findh(a[he].y);
		if(fa!=fb)
		{
			fah[fa]=fb;
			--m;
			ans+=a[he].z;//由于M大于1，所以N一定等于1 
		}
		he++;
	}
	
	
	while(n>1)//横边已经连完，而纵边还没连完，就继续连纵边
	{
		fa=findz(b[zo].x); fb=findz(b[zo].y);
		if(fa!=fb)
		{
			faz[fa]=fb;
			--n;
			ans+=b[zo].z;//由于N大于1，所以M一定等于1 
		}
		zo++;
	}
	
	cout<<maxn-ans<<endl;//最终答案为所有边权值之和减最小生成树的边权值和 
	return 0;
}