首页 > 代码库 > BZOJ 1797 最小割

BZOJ 1797 最小割

2024-07-09 00:26:31   226人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1797

题意：给出一个有向图，每条边有流量，给出源点汇点s、t。对于每条边，询问：（1）是否存在一个最小割包含该边？（2）是否所有的最小割都包含该边？

思路：首先求最大流，在残余网络中求强连通 分量。对于每条原图中的边（最大流中添加的反向边不算）<u,v>，该边的残余流量为0且u和v在两个不同的强连通分量中，则存在一个最小割 包含该边；在上述满足且u与s在一个连通分量、v与t在一个连通分量时所有的最小割包含该边。

 

struct node{    int u,v,cap,id,next;};node edges[N*50];int head[N],e;int pre[N],num[N],h[N],cur[N];int s,t;int Maxflow(int s,int t,int n){    int i;    for(i=0;i<n;i++) cur[i]=head[i];    int u=s,Min,k,v,ans=0;    while(h[u]<n)    {        if(u==t)        {            Min=INF;            for(i=s;i!=t;i=edges[cur[i]].v)            {                k=cur[i];                if(edges[k].cap<Min) Min=edges[k].cap,v=i;            }            ans+=Min; u=v;            for(i=s;i!=t;i=edges[cur[i]].v)            {                k=cur[i];                edges[k].cap-=Min;                edges[k^1].cap+=Min;            }        }        for(i=cur[u];i!=-1;i=edges[i].next)        {            if(edges[i].cap>0&&h[u]==h[edges[i].v]+1) break;        }        if(i!=-1)        {            cur[u]=i;            pre[edges[i].v]=u;            u=edges[i].v;        }        else        {            if(--num[h[u]]==0) break;            cur[u]=head[u];            Min=n;            for(i=head[u];i!=-1;i=edges[i].next)            {                if(edges[i].cap>0&&h[edges[i].v]<Min) Min=h[edges[i].v];            }            h[u]=Min+1;            num[Min+1]++;            if(u!=s) u=pre[u];        }    }    return ans;}int n,m;void add(int u,int v,int w,int id){    edges[e].u=u;    edges[e].v=v;    edges[e].cap=w;    edges[e].id=id;    edges[e].next=head[u];    head[u]=e++;}int dfn[N],low[N],id,Num,color[N],visit[N];stack<int> S;void DFS(int u){    low[u]=dfn[u]=++id;    S.push(u);        int i,v;    for(i=head[u];i!=-1;i=edges[i].next)     {        v=edges[i].v;        if(edges[i].cap<=0) continue;        if(!dfn[v])        {            DFS(v);            low[u]=min(low[u],low[v]);        }        else if(!visit[v])        {            low[u]=min(low[u],dfn[v]);        }    }    if(low[u]==dfn[u])    {        Num++;        do        {            v=S.top();            S.pop();            visit[v]=1;            color[v]=Num;        }while(v!=u);    }}int ans[N*30][2];int main(){    clr(head,-1);    RD(n,m); RD(s,t);    int u,v,w,i;    FOR1(i,m)     {        RD(u,v,w);        add(u,v,w,i);        add(v,u,0,0);    }    Maxflow(s,t,n+1);    FOR1(i,n) if(!visit[i]) DFS(i);    FOR0(i,e)    {        u=edges[i].u;        v=edges[i].v;        w=edges[i].id;        if(color[u]==color[v]) continue;        if(edges[i].cap>0) continue;        ans[w][0]=1;        if(color[u]==color[s]&&color[v]==color[t])         {            ans[w][1]=1;        }    }    FOR1(i,m) PR(ans[i][0],ans[i][1]);}

 

 

 


联系
我们