最小截断[AHOI2009]

【题目描述】

宇宙旅行总是出现一些意想不到的问题，这次小可可所驾驶的宇宙飞船所停的空间站发生了故障，这个宇宙空间站非常大，它由N个子站组成，子站之间有M条单向通道，假设其中第i（1＜＝i＜＝M）条单向通道连接了xi，yi两个中转站，那么xi子站可以通过这个通道到达yi子站，如果截断这条通道，需要代价ci。现在为了将故障的代价控制到最小，小可可必须想出一个截断方案，使a站不能到达b子站，并且截断的代价之和最小。我们称之为最小截断，小可可很快解决了这个故障，但是爱思考的小可可并不局限于此，为了今后更方便的解决同类故障，他考虑对每条单向通道：

1，是否存在一个最小代价路径截断方案，其中该通道被切断？

2，是否对任何一个最小代价路径切断方案，都有该通道被切断？

聪明的你能帮小可可解决他的疑问吗？

 

【输入格式】

第一行有4个整数，依次为N，M，a和b；

第二行到第(m+1)行每行3个正整数x，y，c表示x子站到y子站之间有单向通道相连，单向通道的起点是x终点是y，切断它的代价是c（1＜＝c＜＝10000）；

两个子站之间可能有多条通道直接连接。

 

【输出格式】

对每一个单向通道，按输入的顺序，依次输出一行包含两个非0即1的整数，分别表示对问题一和问题二的回答（其中1表示是，0表示否）。每行两个整数之间用一个空格分隔开。

 

【样例输入】

   6 7 1 6 1 2 31 3 22 4 4 2 5 13 5 5 4 6 25 6 3

【样例输出】

1 0
1 0
0 0
1 0
0 0
1 0
1 0

【提示】

  100％的数据中，N＜＝4000，M＜＝60000

  70％的数据中，N＜＝1000，M＜＝40000

  40％的数据中，N＜＝200，M＜＝2000

 

【题解】

     血帆海盗的进阶版，先贴结论XDDD：

       最小割的必须边
       一定在最小割中的边、扩大容量后能增大最大流的边， ① 满流；② 残余网络中S能到入点、出点能到T。 从S开始DFS、T开始反向DFS，标记到达的点，然后枚举满流边即可。
       最小割的可行边
       被某一种最小割的方案包含的边， ① 满流；② 删掉之后在残余网络中找不到u到v的路径。 在残余网络中tarjan求SCC，(u,v)两点在同一SCC中说明残余网络中存在u到v路径。

      但是在这道题里求必须边好像不能用dfs，上面那个结论已经忘了是从哪里看的了= =，必须边的起点与S在同一个强联通分量里，终点与T在同一个强联通分量里。知道了结论之后就可以放心地跑了。

       写一点理解：残余网络中不能形成强连通分量的只有满流边（或许还有没用到的边？但是那不会被统计答案），所以残余网络缩成DAG的每个s-t割都是原图中的一个最小割，这是可行性。而u、v分别和s、t同处一个强联通分量的边一旦边权增加就会产生增广路径，这恰好符合必须边的定义。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
queue<int> q;
stack<int> s;
const int sj=4010;
const int sm=60010;
int n,m,si,t,a1,a2,a3,e,h[sj],c[sj],dep[sj],dfn[sj],low[sj];
bool r[sj];
struct B
{
    int ne,v,w,u;
}b[sm<<1];
inline int read()
{
    int jg=0,jk=getchar()-'0';
    while(jk<0||jk>9)    jk=getchar()-'0';
    while(jk>=0&&jk<=9)  jg*=10,jg+=jk,jk=getchar()-'0';
    return jg;
}
void add(int x,int y,int z)
{
    b[e].u=x,b[e].v=y,b[e].w=z,b[e].ne=h[x],h[x]=e++;
    b[e].u=y,b[e].v=x,b[e].w=0,b[e].ne=h[y],h[y]=e++;
}
bool bfs(int x)
{
    memset(dep,0,sizeof(dep));
    while(!q.empty())  q.pop();
    dep[x]=1,q.push(x);
    while(!q.empty())
    {
        x=q.front(),q.pop();
        for(int i=h[x];i!=-1;i=b[i].ne)
            if(!dep[b[i].v]&&b[i].w)
            {
                dep[b[i].v]=dep[x]+1;
                if(b[i].v==t)  return 1;
                q.push(b[i].v);
            }
    }
    return 0;
}
int dfs(int x,int f)
{
    if(x==t)  return f;
    int ret=0,d;
    for(int i=h[x];i!=-1;i=b[i].ne)
        if(dep[b[i].v]==dep[x]+1&&b[i].w)
        {
            d=dfs(b[i].v,min(f,b[i].w));
            ret+=d,f-=d;
            b[i].w-=d,b[i^1].w+=d;
            if(!f)  break;
        }
    if(!ret)  dep[x]=-1;
    return ret;
}
void bj(int &x,int y)
{
    x=x<y?x:y;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++a1,r[x]=1,s.push(x);
    for(int i=h[x];i!=-1;i=b[i].ne)
    {
        if(!b[i].w)  continue;
        if(!dfn[b[i].v])  tarjan(b[i].v),bj(low[x],low[b[i].v]);
        else if(r[b[i].v])  bj(low[x],dfn[b[i].v]);
    }
    if(low[x]==dfn[x])
    {
        a2++;
        do
        {
            a3=s.top(),s.pop();
            r[a3]=0,c[a3]=a2;
        }while(a3!=x);
    }
}
int main()
{
    memset(h,-1,sizeof(h));
    n=read(),m=read(),si=read(),t=read();
    for(int i=1;i<=m;i++)
    {
        a1=read(),a2=read(),a3=read();
        add(a1,a2,a3);
    }
    while(bfs(si))  dfs(si,0x7fffffff);
    a1=a2=a3=0;
    for(int i=1;i<=n;i++)
        if(!dfn[i])  tarjan(i);
    for(int i=0;i<e;i+=2)
    {
        if(b[i].w)  printf("0 0\n");
        else
        {
            if(c[b[i].u]!=c[b[i].v])
            {
                if(c[b[i].v]==c[t]&&c[b[i].u]==c[si])  printf("1 1\n");
                else  printf("1 0\n");
            }
            else printf("0 0\n");
        }
    }
    return 0;
}