ABC-270 F - Transportation(kruskal)

ABC-270 F - Transportation(kruskal)

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

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

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

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

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

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

然后跑MST的kruskal即可。

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

#include
#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36