Bzoj1797 ahoi2009最小割

诶我擦今天早晨起晚了。。。。

这个题是昨天睡前过的。。

这个题要求两个东西

一个是最小割的可行边，一个是必须边

可行边：有可能在最小割中的边

必须边：一定在最小割中的边

那么首先要求一次最小割是肯定的

然后首先考虑求出可行边：如果对于一条边，他的两个端点在残余网络中可以互相达到那么这个一定不是答案，但是如果每次询问都一次dfs显然太慢了，所以我们可以利用tarjan求出强连通分量，如果一个边的两个点在不同的强联通分量中那么这就是可行边

最后考虑必须边，这个边的左端点一定和s是联通的，右端点一定和t是联通的，所以只需要判断一下就可以了

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<stack>
#define maxm 60009
#define maxn 60009
#define inf 0x7fffffff/2
#define rep(i,j,k) for(int i=j;i<=k;i++)
 
using namespace std;
 
int tot=1,n,m,next[2*maxm],head[maxn],value[2*maxm],flow[2*maxm],done[maxn];
int to[2*maxm],ask[maxm][3],ans[maxm][2],dis[maxn],in[maxn];
int dfn[maxn],low[maxn],dfs_clock=0,scc_num=0,scc[maxn],s,t,MaxFlow=0;
 
stack<int>S;
 
void add(int From,int To,int weight)
{
    to[++tot]=To;
    next[tot]=head[From];
    head[From]=tot;
    value[tot]=flow[tot]=weight;
 
    to[++tot]=From;
    next[tot]=head[To];
    value[tot]=flow[tot]=0;
    head[To]=tot;
}
 
bool bfs()
{
    memset(done,0,sizeof(done));
    queue<int>q;
    done[s]=1;
    dis[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=head[now];i;i=next[i])
            if(!done[to[i]]&&flow[i]>0)
                done[to[i]]=1,dis[to[i]]=dis[now]+1,q.push(to[i]);
    }
    return done[t];
}
 
int dfs(int x,int a)
{
    if(x==t||!a)
        return a;
    int f,Return=0;
    for(int i=head[x];i;i=next[i])
    {
        int y=to[i];
        if(dis[y]==dis[x]+1&&(f=dfs(y,min(a,flow[i])))>0)
        {
            flow[i]-=f,flow[i^1]+=f,Return+=f,a-=f;
            if(!a)
                return Return;
        }
    }
    return Return;
}
 
void tarjan(int x)
{
    in[x]=1;
    dfn[x]=low[x]=++dfs_clock;
    S.push(x);
    for(int i=head[x];i;i=next[i])
        if(flow[i]>0)
        {
            if(!dfn[to[i]])
            {
                tarjan(to[i]);
                low[x]=min(low[x],low[to[i]]);
            }
            else
                if(in[to[i]])
                    low[x]=min(low[x],dfn[to[i]]);
        }
 
    if(dfn[x]==low[x])
    {
        scc_num++;
        while(!S.empty())
        {
            int now=S.top();
            S.pop();
            scc[now]=scc_num;
            in[now]=0;
            if(now==x)
                break;
        }
    }
    return;
}
 
int main()
{
    scanf("%d%d%d %d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&ask[i][0],&ask[i][1],&ask[i][2]),add(ask[i][0],ask[i][1],ask[i][2]);
 
    while(bfs())
        MaxFlow+=dfs(s,inf);
     
    memset(scc,0,sizeof(scc));
    rep(i,1,n)
        if(!dfn[i])
            tarjan(i);
 
    for(int i=2;i<=tot;i+=2)
    {
        if(!flow[i]&&scc[to[i]]!=scc[to[i^1]])
            printf("1");
        else
            printf("0");
        if(!flow[i]&&scc[to[i^1]]==scc[s]&&scc[to[i]]==scc[t])
            printf(" 1\n");
        else
            printf(" 0\n");
    }
    return 0;
}

Bzoj1797 ahoi2009最小割,布布扣,bubuko.com

Bzoj1797 ahoi2009最小割

原文：http://blog.csdn.net/wbysr/article/details/22843057