ABC-270 F - Transportation(kruskal)

ABC-270 F - Transportation(kruskal)

考虑等价转换，建立两个虚点(分别表示airport和harbor的中转站)。

这样就可以把点统一为边权问题。

对于操作1和操作2，就是等价于向虚点连边。

那么就变成给定条边求连通的MST问题。

这里值得注意的是，我们并不要求虚点一定要在连通块里。

因此需要分4种情况讨论，二进制枚举即可(两个虚点是否在连通块里)。

然后跑MST的kruskal即可。

如枚举时，某个虚点不在树中，那么对应的边直接跳过。否则就按照MST的原则贪心选择即可。
时间复杂度：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,f[201000];
struct qq{
  int u,v,w;
}a[1001000];
int F(int x){
  if(x==f[x])return x;
  return f[x]=F(f[x]); 
}
bool cmp(qq a,qq b){return a.w<b.w;}
bool check(int x,int y){
  if(x<=n)return 0;
  x-=n+1;
  return (y>>x)&1;
}
int main(){
  scanf("%d%d",&n,&m);int M=m;
  for(int i=1,x;i<=n;i++)scanf("%d",&x),a[++M]=(qq){n+1,i,x};
  for(int i=1,y;i<=n;i++)scanf("%d",&y),a[++M]=(qq){n+2,i,y};
  for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
  sort(a+1,a+M+1,cmp);
  ll ans=1e18;
  for(int st=0;st<4;st++){
    for(int i=1;i<=n+2;i++)f[i]=i;
    ll sz=0;int os=0,ok=n-1+!(st>>1)+!(st&1);
    for(int i=1;i<=M;i++)if(F(a[i].u)!=F(a[i].v)){
      if(check(a[i].u,st)||check(a[i].v,st))
               continue;
      f[F(a[i].u)]=F(a[i].v),sz+=a[i].w,os++;
    }
    if(os==ok)ans=min(ans,sz);
  }
  return printf("%lld",ans),0;
}