CQOI 2016 不同的最小割

时间：2022-06-07 10:14:26

题目大意：一个无向图，求所有点对不同的最小割种类数

最小割最多有n-1个，这n-1个最小割构成一个最小割树

分治法寻找n-1个最小割。对于当前点集X，任选两点为ST做最小割，然后找出与S相连的所有点和与T相连的所有点构成S集与T集，更新S集与T集的最小割。然后递归处理两个集合。

最后将最小割排序，找出有多少不同最小割即可

#include<bits/stdc++.h>

#define inf 0x7ffffff

using namespace std;

inline int read(){

    int s=;char ch=getchar();

    for(;ch<''||ch>'';ch=getchar());

    for(;ch>=''&&ch<='';ch=getchar())s=s*+ch-'';

    return s;

}

struct edge{

    int to,next;

    int cap;

}G[];

int tot=,h[],S,T;

void add(int x,int y,int z){

    tot++;G[tot].to=y;G[tot].next=h[x];G[tot].cap=z;h[x]=tot;

}

int vis[],mark[];

int a[];

int n,m;

set<int>s;

bool bfs(){

    memset(vis,,sizeof(vis));

    queue<int>Q;Q.push(S);vis[S]=;

    while(!Q.empty()){

        int u=Q.front();Q.pop();

        for(int i=h[u];i;i=G[i].next){

            int v=G[i].to;

            if(vis[v]||G[i].cap<=)continue;

            vis[v]=vis[u]+;

            Q.push(v);

        }

    }return vis[T];

}

int dfs(int u,int w){

    if(u==T||w==)return w;

    int flow=;

    for(int i=h[u];i;i=G[i].next){

        int v=G[i].to;

        if(vis[v]!=vis[u]+||G[i].cap<=)continue;

        if(int t=dfs(v,min(w,G[i].cap))){

            G[i].cap-=t;G[i^].cap+=t;

            flow+=t;w-=t;

            if(!w)break;

        }

    }

    if(!flow)vis[u]=;

    return flow;

}

int dinic(){

    int f=;

    while(bfs())f+=dfs(S,inf);

    return f;

}

void dfs(int x){

    mark[x]=;

    for(int i=h[x];i;i=G[i].next)

        if(G[i].cap&&!mark[G[i].to])

            dfs(G[i].to);

}

void clear(){

    for(int i=;i<=tot;i+=)

        G[i].cap=G[i^].cap=(G[i].cap+G[i^].cap)/;

}

int tmp[];

void solve(int l,int r){

    if(l==r)return;

    clear();

    S=a[l],T=a[r];

    int t=dinic();

    s.insert(t);

    memset(mark,,sizeof(mark));

    dfs(S);

    int L=l,R=r;

    for(int i=l;i<=r;++i)

        if(mark[a[i]])tmp[L++]=a[i];

        else tmp[R--]=a[i];

    for(int i=l;i<=r;++i)a[i]=tmp[i];

    solve(l,L-);solve(R+,r);

}

int main(){

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

    for(int i=;i<=m;++i){

        int u=read(),v=read(),w=read();

        add(u,v,w);add(v,u,w);

    }

    for(int i=;i<=n;++i)a[i]=i;

    solve(,n);

    printf("%d\n",s.size());

    return ;

}

相关文章