自动搬运

查看原文

来自洛谷，原作者为

	Marser 所有的苦难与背负尽头，都是行云流水般的此世光阴。

搬运于2025-08-24 21:52:06，当前版本为作者最后更新于2020-03-30 22:01:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：最小割树。没有这东西不知道怎么写这道题。

题意

给定一张无向图，每个点有点权。每次给定一个 $x$，询问当限制选出的点集权值和 $\ge x$ 时最大的整数 $k$，满足点集内任意两点间均有至少 $k$ 条不相交路径。

题解

首先，我们可以将“两点间有至少 $k$ 条不相交路径”转化为“以两点为源、汇，最大流量不小于 $k$ ”。运用最大流最小割定理转化为“两点间最小割不小于 $k$ ”，我们就自然地联想到最小割树。
首先跑一遍最小割树，记录下所有树边，将它们按边权从大到小排序，同时将所有询问按 $x$ 值从小到大排序。用带权并查集维护每个点所在联通块的点权和，依次加入每一条边，并更新单个连通块的点权和最大值 $cur$。每次加完边，我们可以将所有满足 $x \le cur$ 且未被处理的询问的答案更新为当前边的权值。注意特殊处理输出nan的情况。
主要的复杂度瓶颈在求最小割树的过程，相信自己能过就好了。
感觉是道不错的最小割树练习题。

代码

#include<bits/stdc++.h>
#define reg register
typedef long long ll;
using namespace std;
const int MN=555;
const int MM=12005;
const int MQ=2020;
const int inf=0x3f3f3f3f;
int to[MM],nxt[MM],c[MM],flow[MM],h[MN],cnt;
inline void ins(int s,int t,int w,int f){
	to[cnt]=t;nxt[cnt]=h[s];c[cnt]=w;
	flow[cnt]=f;h[s]=cnt++;
}
int n,m;
namespace Flow{
	int S,T,iter[MN],level[MN],que[MN];
	bool bfs(){
		memset(level,-1,sizeof(level));
		reg int he=0,ta=0;
		que[ta++]=S;level[S]=0;
		while(he<ta){
			reg int v=que[he++];
			for(reg int i=h[v];~i;i=nxt[i])
				if((c[i]-flow[i])&&level[to[i]]<0)
					level[to[i]]=level[v]+1,que[ta++]=to[i];
		}
		return ~level[T];
	}
	int dfs(int st,int f){
		if(st==T)return f;
		reg int used=0,w;
		for(reg int& i=iter[st];~i;i=nxt[i])
			if((c[i]-flow[i])&&level[to[i]]>level[st]){
				w=dfs(to[i],min(f-used,c[i]-flow[i]));
				if(!w)continue;
				flow[i^1]-=w;flow[i]+=w;used+=w;
				if(f==used)return f;
			}
		return used;
	}
	int Dinic(int ss,int tt){
		S=ss;T=tt;reg int res=0,f;
		for(reg int i=0;i<cnt;i++)
			flow[i]=(~i&1)*c[i];
		while(bfs()){
			memcpy(iter,h,sizeof(h));
			while(f=dfs(S,inf))res+=f;
		}
		return res;
	}
}
int node[MN],t1[MN],t2[MN],col[MN],idx;
void paint(int st){
	col[st]=idx;
	for(reg int i=h[st];i;i=nxt[i])
		if((c[i]-flow[i])&&col[to[i]]<idx)paint(to[i]);
}
struct edge{int s,t,w;}es[MN];
struct data{int x,id;}ask[MQ];
int q,ecnt,wei[MN],par[MN],ans[MQ];
void solve(int l,int r){
	if(l==r)return;
	reg int val=Flow::Dinic(node[l],node[l+1]);
	idx++;paint(node[l]);
	es[++ecnt]=(edge){node[l],node[l+1],val};
	reg int cnt1=0,cnt2=0;
	for(reg int i=l;i<=r;i++){
		if(col[node[i]]==idx)t1[++cnt1]=node[i];
		if(col[node[i]]!=idx)t2[++cnt2]=node[i];
	}
	for(reg int i=1;i<=cnt1;i++)node[i+l-1]=t1[i];
	for(reg int i=1;i<=cnt2;i++)node[i+l+cnt1-1]=t2[i];
	solve(l,l+cnt1-1);solve(l+cnt1,r);
}
inline int find(int x){return par[x]==x?x:par[x]=find(par[x]);}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	memset(h,-1,sizeof(h));
	for(reg int i=1;i<=n;i++)scanf("%d",wei+i);
	for(reg int i=1,s,t;i<=m;i++){
		scanf("%d%d",&s,&t);
		ins(s,t,1,0);ins(t,s,1,1);
		ins(t,s,1,0);ins(s,t,1,1);
	}
	for(reg int i=1;i<=n;i++)node[i]=i;
	solve(1,n);
	for(reg int i=1;i<=q;i++)scanf("%d",&ask[i].x),ask[i].id=i;
	sort(es+1,es+n,[](edge a,edge b){
		return a.w>b.w;
	});
	sort(ask+1,ask+1+q,[](data a,data b){
		return a.x<b.x;
	});
	reg int Ans=0,cur=1;
	for(reg int i=1;i<=n;i++)par[i]=i,Ans=max(Ans,wei[i]);
	memset(ans,0x3f,sizeof(ans));
	for(;cur<=q&&ask[cur].x<=Ans;cur++)ans[ask[cur].id]=0;
	for(reg int i=1,s,t;i<n;i++){
		s=find(es[i].s);t=find(es[i].t);
		par[t]=s;Ans=max(Ans,wei[s]+=wei[t]);
		for(;cur<=q&&ask[cur].x<=Ans;cur++)
			ans[ask[cur].id]=es[i].w;
	}
	for(reg int i=1;i<=q;i++){
		if(ans[i]==inf)puts("Nuclear launch detected");
		else if(ans[i]==0)puts("nan");
		else printf("%d\n",ans[i]);
	}
	return 0;
}