[洛谷]P3729 曼哈顿计划EX（最小割树/等价流树）

时间：2020-12-17 18:37:23

题目大意：给出一张n个点m条边的无向图，每个点有点权，q次询问，每次给出k，要求选出若干个点点权之和不小于k，求一个最大的值x，使得选出的点中任意两点之间至少有x条互不相交的链。（n<=550,m<=3000,q<=2017）

当时看到这题一看就不可做 看了题解说什么等价流树也看不懂 后来FallDream大佬做了一题最小割树 看了看网上大神极短的说明加上自己大量的脑补终于搞懂了这玩意儿 另外貌似等价流树就是最小割树

最小割树的思路大概是先任意求出两点之间的最小割，并把整张图按最小割分成两个部分，并用这个最小割更新所有被分到不同部分的点对之间的最小割，然后对分出的两个部分分治，值得注意的是即使点集被分治分小了，每次我们更新答案仍然要更新整张图。

通过这个分治过程，我们会得到n-1个最小割，并能组成一个树形结构，每次求两点之间最小割时，两点之间连边，边权为最小割，图上任意两点之间的最小割就是树上路径的最小值，这样我们只要做O(n)次网络流就能求出O(n^2)个点对之间的最小割。

下面考虑这题，两点之间至少有x条不相交的链就是说最大流/最小割大等x，假设我们选出了若干个点，那么这些点两两之间最小割的最小值，就是在等价流树上要让这些点连通所必要的边的最小值，我们把等价流树上的边从大到小加进带权并查集，维护各个连通块的权值和，问题即可解决。

自己乱写了一个比较舒服的模板。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

inline int read()

{

    int x;char c;

    while((c=getchar())<''||c>'');

    for(x=c-'';(c=getchar())>=''&&c<='';)x=x*+c-'';

    return x;

}

#define MN 550

#define MM 3000

#define INF 0x7FFFFFFF

struct edge{int nx,t,w;}e[MM*+];

int m,S,T,h[MN+],en,d[MN+],q[MN+],qn,c[MN+];

int w[MN+],uu[MM+],vv[MM+],cnt,f[MN+],ans[MM+];

vector<int> v[MN+];

struct tredge{int u,v,w;}t[MN+];

bool cmp(tredge a,tredge b){return a.w>b.w;}

struct query{int k,id;}r[MM+];

bool cmpk(query a,query b){return a.k<b.k;}

int gf(int k){return f[k]?f[k]=gf(f[k]):k;}

inline void ins(int x,int y)

{

    e[++en]=(edge){h[x],y,};h[x]=en;

    e[++en]=(edge){h[y],x,};h[y]=en;

}

bool bfs()

{

    int i,j;

    memset(d,,sizeof(d));

    for(d[q[i=qn=]=S]=;i<=qn;++i)for(j=c[q[i]]=h[q[i]];j;j=e[j].nx)

        if(e[j].w&&!d[e[j].t])d[q[++qn]=e[j].t]=d[q[i]]+;

    return d[T];

}

int dfs(int x,int r)

{

    if(x==T)return r;

    int k,u=;

    for(int&i=c[x];i;i=e[i].nx)if(e[i].w&&d[x]+==d[e[i].t])

    {

        k=dfs(e[i].t,min(r-u,e[i].w));

        u+=k;e[i].w-=k;e[i^].w+=k;

        if(u==r)return u;

    }

    return d[x]=,u;

}

void color(int x)

{

    c[x]=;

    for(int i=h[x];i;i=e[i].nx)

        if(e[i].w&&!c[e[i].t])color(e[i].t);

}

void build(int x)

{

    if(v[x].size()<)return;

    t[++cnt].u=S=x;t[cnt].v=T=v[x][v[x][]==x];

    memset(h,,sizeof(h));en=;

    for(int i=;i<=m;++i)ins(uu[i],vv[i]);

    while(bfs())t[cnt].w+=dfs(S,INF);

    memset(c,,sizeof(c));

    color(x);

    for(int i=;i<v[x].size();++i)while(i<v[x].size()&&!c[v[x][i]])

        v[T].push_back(v[x][i]),v[x].erase(v[x].begin()+i);

    build(T);build(x);

}

int main()

{

    int n,q,i,j,k=;

    n=read();m=read();q=read();

    for(i=;i<=n;++i)k=max(k,w[i]=read()),v[].push_back(i);

    for(i=;i<=m;++i)uu[i]=read(),vv[i]=read();

    for(i=;i<=q;++i)r[i]=(query){read(),i};

    build();

    sort(r+,r+q+,cmpk);

    sort(t+,t+n,cmp);

    for(j=;j<=q&&r[j].k<=k;++j)ans[r[j].id]=INF;

    for(i=;i<n;++i)

    {

        k=max(k,w[gf(t[i].u)]+=w[gf(t[i].v)]);

        f[gf(t[i].v)]=gf(t[i].u);

        for(;j<=q&&r[j].k<=k;++j)ans[r[j].id]=t[i].w;

    }

    for(i=;i<=q;++i)

        if(ans[i]==INF)puts("nan");

        else if(ans[i])printf("%d\n",ans[i]);

        else puts("Nuclear launch detected");

}

相关文章