题解 P4809 【[CCC 2018]最大战略储备】
VictorYuan · · 题解
本蒟蒻的第一篇题解。
写题解原因：（看题解的同学可以跳过）
我在考试的时候的一道题与这道题十分相似，场上写出了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;
}