Title: BZOJ-1797

Problem Solution: About Minimum Cut Can Go Here Look, the explanation of the form of dialogue is quite clear.

For this topic:

1. The cut-off scheme of minimum path strength: that is, the minimum cut. If the package does not include this edge, that is, whether there is one of the cut-off schemes that contains this edge.
2. The size of the throughflow== the minimum cut size. A network flow value corresponds to several minimum cut schemes.
3.Dinic algorithm finishes running to get the network flow value and deletes all full-flow edges in the graph. Minimum cut must be composed of full-flow edges, but not any full-flow edges can be 4. Minimum cut can be made up of all full-flow edges.
4. There are many connected blocks in the residual graph after the Dinic algorithm runs. If the beginning and end of an edge are in two different connected blocks, then the edge is full flow and constitutes the maximum flow, then he can participate in the formation of the minimum cut. If the starting point of this edge is in the connected block where s is, the end point is in t. In a connected block, the full stream edge must be deleted and the minimum cut must be constructed.

(equivalent to: (1) for any full stream edge (u,v), (u,v) can appear in a minimum cut set if and only if id[u]!=id[v];
(2) For any full stream edge (u,v), (u,v) must appear in the minimum cut set if and only if Id [u]= ID [s] and ID [v]= ID [t].

Then this problem can be solved by running Dinic once to get the residual map, then running Tarjan in the residual map to find the link block, recording the number of the link block where the node is located, and then querying the link by the side.~

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#define N 100005
#define M 100005
#define INF 0x7fffffff
using namespace std;
int n,m,s,t,c,tot,num;
int head[N],cur[N],dfn[N],low[N],deep[N],belong[N];
bool vis[N];
struct ljh
{
    int next,to,w,from;
}e[2*M];
stack<int>ss;
inline void add(int x,int y,int z)
{
    e[c].next=head[x];
    e[c].from=x;
    e[c].to=y;
    e[c].w=z;
    head[x]=c++;
}
inline void init()
{
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
    memset(belong,0,sizeof(belong));
    tot=0;
    c=0;
    num=0;
}
bool bfs(int s,int t)
{
    queue<int>q;
    memset(deep,0,sizeof(deep));
    deep[s]=1;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            int nex=e[i].to;
            if(e[i].w!=0&&deep[nex]==0)
            {
                deep[nex]=deep[x]+1;
                q.push(nex);
            }
        }
    }
    return deep[t]!=0;
}
int dfs(int x,int t,int maxflow)
{
    if(x==t)return maxflow;
    int ans=0;
    for(int i=cur[x];i!=-1;i=e[i].next)
    {
        int nex=e[i].to;
        if(deep[nex]!=deep[x]+1||ans>=maxflow||e[i].w<=0)continue;
        cur[x]=i;
        int k=dfs(nex,t,min(e[i].w,maxflow-ans));
        e[i].w-=k;
        e[i^1].w+=k;
        ans+=k;
    }
    if(ans==0)deep[x]=-2;
    return ans;
}
void Dinic(int s,int t)
{
    while(bfs(s,t))
    {
        memcpy(cur,head,sizeof(head));
        dfs(s,t,INF);
    }
}
void Tarjan(int x)
{
    low[x]=dfn[x]=++tot;
    ss.push(x);
    vis[x]=1;
    for(int i=head[x];i!=-1;i=e[i].next)
    {
        if(e[i].w)//Judging from this, this side must be a residual edge to update the link block.
        {
		    int v=e[i].to;
		    if(!dfn[v])
		    {
		        Tarjan(v);
		        low[x]=min(low[x],low[v]);
		    }
		    else if(vis[v]==1)low[x]=min(low[x],dfn[v]);
        }
    }
    if(low[x]==dfn[x])//Notice here. Find bug s and find autism.
    {
        int nex;
        num++;
        do
        {
            nex=ss.top();
            ss.pop();
            vis[nex]=0;
            belong[nex]=num;
        }while(!ss.empty()&&nex!=x);
    }
    return;
}
int main()
{
    while(~scanf("%d%d%d%d",&n,&m,&s,&t))
    {
        init();
        for(int i=1;i<=m;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,z);
            add(y,x,0);
        }
        Dinic(s,t);
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                Tarjan(i);
        for(int i=0;i<c;i+=2)
        {
            if(e[i].w>0)printf("0 0\n");//That means that side hasn't gone at all.
            else
            {
                if(belong[e[i].from]!=belong[e[i].to])printf("1 ");
                else printf("0 ");
                if(belong[e[i].from]==belong[s]&&belong[e[i].to]==belong[t])printf("1\n");
                else printf("0\n");
            }
        }
    }
 }