http://www.usaco.org/index.php?page=viewproblem2&cpid=625
题意：
有一个(0,0)(A,B)的矩阵，然后有n条横线，m条竖线。这些线的交点之间的线段可以被一次性删除。这些线得到了(n+1)(m+1)个空间，问让所有空间联通的删除线总长度最少。
代码：
由克鲁斯卡尔得最小生成树可知，所有线段之间，从小到大删除是没问题的。
可以一组线同时删除： 删除时可能有一些空间本身就联通，例如下图中尝试删除当前列时，134已经联通，所以只需要删除 4 − ( 3 − 1 ) 4-(3-1) 4−(3−1)条即可
公式：（cnt2为已经联通的行数量,cnt1为已经联通的列数量） i f ( c n t 1 ∧ c n t 2 ) : a n s + = l e n ∗ ( n − ( c n t 2 − 1 ) ) if(cnt_1\wedge cnt_2):ans+=len*(n-(cnt_2-1)) if(cnt1∧cnt2):ans+=len∗(n−(cnt2−1))
代码：
#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) typedef long long LL; #define pill pair<int,int> #define se second #define fi first const int maxn=5e4+9; void show(int i){ cout<<"show "<<i<<endl; } int cnt; pill p[maxn]; int a[maxn],b[maxn]; int main(){ ios::sync_with_stdio(false); cin.tie(0); int A,B,n,m; cin>>A>>B>>n>>m; LL ans=0; rep(i,1,n)cin>>a[i]; rep(i,1,m)cin>>b[i]; sort(a+1,a+1+n); sort(b+1,b+1+m); int pre=0; rep(i,1,n){ p[++cnt]={a[i]-pre,1}; pre=a[i]; } p[++cnt]={A-pre,1}; pre=0; rep(i,1,m){ p[++cnt]={b[i]-pre,2}; pre=b[i]; } p[++cnt]={B-pre,2}; sort(p+1,p+1+cnt); // rep(i,1,cnt){ // cout<<p[i].fi<<" "<<p[i].se<<endl; // } int cnt_1=0,cnt_2=0; rep(i,1,cnt){ if(p[i].se==1){ if(cnt_2&&cnt_1){ //cout<<"line1 "<<p[i].fi<<",ans+="<<1ll*p[i].fi*(m+1-cnt_2)<<endl; ans+=1ll*p[i].fi*(m+1-cnt_2); } else{ //cout<<"line2 "<<p[i].fi<<",ans+="<<1ll*p[i].fi*m<<endl; ans+=1ll*p[i].fi*m; } cnt_1++; } else{ if(cnt_1&&cnt_2){ //cout<<"col1 "<<p[i].fi<<",ans+="<<p[i].fi*(n+1-cnt_1)<<endl; ans+=1ll*p[i].fi*(n+1-cnt_1); } else{ //cout<<"col2 "<<p[i].fi<<",ans+="<<p[i].fi*n<<endl; ans+=1ll*p[i].fi*n; } cnt_2++; } } cout<<ans<<endl; }