题目链接；
1.题外话
停课了。刷刷之前的题可以RP++；
2.解题意
n*m，很规则的期盼图。
a[]表示水平相邻两个点之间点的边权，b[]则是竖着两个点之间的边权值。
每一个都只给你n/m个数据，表明这一行/列的边权值全都相同。
题目就是让你求这么一个图的最小生成树的边权值之和。
3.找思路
习惯性的浏览一下数据范围。如果暴力的话克鲁斯卡尔肯定是跑不过的，只能拿部分分。想要拿满分，肯定要用到题目给我们的特殊性质。
考虑一下克鲁斯卡尔的原理：边权从小到大排序，如果遇到能成环的就跳过，否则就把边加入到最小生成树中。
对于这道题，因为它一行，一列上的边权全部相同，那么他们被加入到最小生成树的概率是等价的。
如果你假设每一行的边都加入了最小生成树，那么此时一定存在一个扩充生成树的方案：
把列中权值最小的竖着的边加入进去，如下图（红色边表示已经被加入到最小生成树中）：
选取权值最小的一列加入：
这样一来，才是最小生成树。
同样，对于列都选满的情况，权值最小的行也一定会被加入到生成树中来。
那么首先，sort一遍a，b，把权值最小的（下标为1）的边加入到最小生成树中来。因为这些边是一定会加入进来的；
这里的加边是可以降低复杂度的，因为一行/一列会被同时加入进来。
考虑之后的做法：
一个显然的想法是从行列综合考虑，按照权值从小到大加如一行/一列边。因为如果不选这个权值较小的，sort后下标更大的边将不会比它更优；
然后呢我们遇到一个很明显的阻碍：判环。
解决方法也很简单：我们不在一整列一整行地加入进入，而是除去那些 连接之前已经被加入的行/列的边后加入。
语言描述不当，画图理解来补：
假如我们已经选好了行和列中最优的：
接下来我们发现a[2]>b[2]，也就是这时候列比行更优，我们尝试尽可能多的加入这一行：
（注意：b[2]不一定是第二列哦）
因为第三行是“之前已经被加入的行”，那么我们必须要舍去其中一条连接它与当前这一列。也就是说，图中绿色的列要舍去一个。由于我们要的答案是权值和而不是具体的选择方案，那么这两条边选哪个也就无所谓了。计算权值时我们只需把边数减一即可。
就这样进行下去，直到n行/m列其中一个被选满为止。宣告结束，最小生成树生成。
4.代码
#include<cstdio> #include<algorithm> #define N 300007 #define ll long long using namespace std; int n,m,a[N],b[N]; ll ans=0; inline int read() { int ans=0; char ch=getchar(),last=' '; while(ch>'9'||ch<'0')last=ch,ch=getchar(); while(ch>='0'&&ch<='9')ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); return last=='-'?-ans:ans; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { a[i]=read(); } for(int i=1;i<=m;i++) { b[i]=read(); } sort(a+1,a+1+n); sort(b+1,b+1+m); ans+=(ll)a[1]*(m-1)+(ll)b[1]*(n-1); int l=1,h=1,cnt1=2,cnt2=2; while(cnt1<=n&&cnt2<=m) { if(a[cnt1]<=b[cnt2])ans+=(ll)a[cnt1++]*(m-l),h++; else ans+=(ll)b[cnt2++]*(n-h),l++; } printf("%lld",ans); }
希望对各位有所帮助。
祝NOIP2020rp++