题解 P3729 【曼哈顿计划EX】

· · 题解

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

题意

给定一张无向图，每个点有点权。每次给定一个 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;
}