LibreOJ2042 - 「CQOI2016」不同的最小割

Description

给出一个给出一个\(n(n\leq850)\)个点\(m(m\leq8500)\)条边的无向图。定义\(cut(s,t)\)等于\(s,t\)的最小割的容量，求在所有\(cut(s,t)\)中不同的值有多少个。

Solution

有一个我也想不好为什么的性质：若\(s,t\)的最小割将原图划分成\(S,T\)两个集合，那么\(\forall u\in S,v\in T\)，有\(cut(u,v)=cut(s,t)\)。那么我们可以用分治来做。

对于一个点集\(V\)，随便选择两个不同的点\(s,t\)并求出最小割和集合\(S,T\)。接下来只要分别考虑\(S\)内部的最小割和\(T\)内部的最小割即可。

我们可以用一个数组\(seq\)上的一个区间\([L,R]\)来代表集合。每次求出\(S,T\)后将\(seq[L..R]\)按\(S\)在前\(T\)在后的顺序重排，这样\(S\)和\(T\)也可以用序列上的区间表示了。

Code

//「CQOI2016」不同的最小割

#include <bits/stdc++.h>

using namespace std;

inline char gc()

{

    static char now[1<<16],*s,*t;

    if(s==t) {t=(s=now)+fread(now,1,1<<16,stdin); if(s==t) return EOF;}

    return *s++;

}

inline int read()

{

    int x=0; char ch=gc();

    while(ch<'0'||'9'<ch) ch=gc();

    while('0'<=ch&&ch<='9') x=x*10+ch-'0',ch=gc();

    return x;

}

const int N=1e3;

const int INF=0x3F3F3F3F;

int n,m;

int edCnt,h[N];

struct edge{int v,c,nxt;} ed[20*N];

int s,t;

void edAdd(int u,int v,int c)

{

    edCnt++; ed[edCnt].v=v,ed[edCnt].c=c,ed[edCnt].nxt=h[u],h[u]=edCnt;

    edCnt++; ed[edCnt].v=u,ed[edCnt].c=c,ed[edCnt].nxt=h[v],h[v]=edCnt;

}

int dpt[N]; int op,cl,Q[N];

bool bfs()

{

    memset(dpt,0,sizeof dpt);

    op=cl=0; dpt[s]=1,Q[++cl]=s;

    while(op<cl)

    {

        int u=Q[++op]; if(u==t) break;

        for(int i=h[u];i;i=ed[i].nxt)

        {

            int v=ed[i].v;

            if(!dpt[v]&&ed[i].c) dpt[v]=dpt[u]+1,Q[++cl]=v;

        }

    }

    return dpt[t];

}

int fill(int u,int in)

{

    if(u==t||in==0) return in;

    int out=0;

    for(int i=h[u];i;i=ed[i].nxt)

    {

        int v=ed[i].v,c=ed[i].c;

        if(!c||dpt[v]!=dpt[u]+1) continue;

        int fl=fill(v,min(in-out,c));

        if(fl==0) dpt[v]=0;

        else ed[i].c-=fl,ed[i^1].c+=fl,out+=fl;

        if(in==out) break;

    }

    return out;

}

int Dinic()

{

    for(int i=2;i<=edCnt;i+=2) ed[i].c=ed[i^1].c=(ed[i].c+ed[i^1].c)>>1;

    int r=0;

    while(bfs()) r+=fill(s,INF);

    return r;

}

int cnt,seq[N],tmp[N];

int ansCnt,ans[N];

void solve(int L,int R)

{

    if(L==R) return;

    s=seq[L+R>>1],t=seq[R]; ans[++ansCnt]=Dinic();

    int op=L-1,cl=R+1;

    for(int i=L;i<=R;i++) tmp[dpt[seq[i]]?++op:--cl]=seq[i];

    for(int i=L;i<=R;i++) seq[i]=tmp[i];

    solve(L,op),solve(cl,R);

}

int main()

{

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

    edCnt=1;

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

    {

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

        edAdd(u,v,w);

    }

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

    solve(1,n);

    sort(ans+1,ans+ansCnt+1);

    printf("%d\n",unique(ans+1,ans+ansCnt+1)-ans-1);

    return 0;

}

巴特西

LibreOJ2042 - 「CQOI2016」不同的最小割

Description

Solution

Code

最新文章

热门文章