F - Transportation
一天遇到两道生成树的题目，还都不会做，菜哭的一天。
这题的做法是另外建两个点n+1，n+2，然后做生成树，因为我们只要前n个点联通就行，后面两个点不一定，那么枚举一下就行。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N=2e5+5;
const ll inf=1ll<<60;
struct node{
ll x,y,v;
};
node e[N*3];
ll tot;
ll x[N],y[N];
ll a[N],b[N],c[N],n,m,f[N],s[N],f1,f2,ans=inf;
bool cmp(node a,node b){
return a.v<b.v;
}
ll find(ll x){
if (x==f[x]) return x;
return f[x]=find(f[x]);
}
void work(){
sort(e+1,e+tot+1,cmp);
fo(i,1,n+2) f[i]=i,s[i]=1;
ll sum=0;
fo(i,1,tot) {
f1=find(e[i].x);
f2=find(e[i].y);
if (f1^f2){
f[f1]=f2;
s[f2]+=s[f1];
sum+=e[i].v;
}
}
f1=find(1);
if (s[f1]>=n) ans=min(ans, sum);
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%lld %lld",&n,&m);
fo(i,1,n) scanf("%lld",&x[i]);
fo(i,1,n) scanf("%lld",&y[i]);
fo(i,1,m) {
scanf("%lld %lld %lld",&a[i],&b[i],&c[i]);
}
fo(s,0,3) {
tot=0;
if (s&1) fo(i,1,n) e[++tot]=(node){i,n+1,x[i]};
if (s&2) fo(i,1,n) e[++tot]=(node){i,n+2,y[i]};
fo(i,1,m) e[++tot]=(node){a[i],b[i],c[i]};
work();
}
printf("%lld",ans);
return 0;
}