Description
A,B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路。设其中第i (1≤i≤M)条道路连接了vi,ui两个中转站，那么中转站vi可以通过该道路到达ui中转站，如果切断这条道路，需要代价ci。现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小。 小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题： 问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？ 问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？ 现在请你回答这两个问题。
Input
第一行有4个正整数，依次为N,M,s和t。第2行到第(M+1)行每行3个正 整数v,u,c表示v中转站到u中转站之间有单向道路相连，单向道路的起点是v， 终点是u,切断它的代价是c(1≤c≤100000)。 注意:两个中转站之间可能有多条道路直接相连。 同一行相邻两数之间可能有一个或多个空格。
Output
对每条单向边，按输入顺序，依次输出一行，包含两个非0即1的整数，分 别表示对问题一和问题二的回答(其中输出1表示是，输出0表示否)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
Sample Input
6 7 1 6
1 2 3
1 3 2
2 4 4
2 5 1
3 5 5
4 6 2
5 6 3
Sample Output
1 0
1 0
0 0
1 0
0 0
1 0
1 0
HINT
设第(i+1)行输入的边为i号边，那么{1,2},{6,7},{2,4,6}是仅有的三个最小代价切割方案。它们的并是{1,2,4,6,7}，交是 。 【数据规模和约定】 测试数据规模如下表所示 数据编号 N M 数据编号 N M 1 10 50 6 1000 20000 2 20 200 7 1000 40000 3 200 2000 8 2000 50000 4 200 2000 9 3000 60000 5 1000 20000 10 4000 60000
2015.4.16新加数据一组，可能会卡掉从前可以过的程序。
同之前的那篇题解
最小割的可行边的充分必要条件：网络流中满流且残余网络中边的2点不在一个scc中。
必行边：是可行边，且残余网络与s，t点分别在一个联通块
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <cstdlib>
#include <queue>
#include <stack>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a).size())
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define MAXN (4000*2+100)
#define MAXM (60000*2+10)
int n,k;
class tar{
public:
vi G[MAXN],G2[MAXN];
int pre[MAXN],lowlink[MAXN],sccno[MAXN],dfs_clock,scc_cnt;
stack<int> S;
void dfs(int u) {
pre[u] = lowlink[u] = ++dfs_clock;
S.push(u);
int sz=SI(G[u]);
Rep(i,sz) {
int v=G[u][i];
if (!pre[v]) {
dfs(v);
lowlink[u]=min(lowlink[u],lowlink[v]);
} else if (!sccno[v]) {
lowlink[u]=min(lowlink[u],pre[v]);
}
}
if (lowlink[u]==pre[u]) {
scc_cnt++;
while(1) {
int x=S.top();S.pop();
sccno[x]=scc_cnt;
if (x==u) break;
}
}
}
void find_scc(int n) {
dfs_clock = scc_cnt = 0;
MEM(sccno)
MEM(pre)
Rep(i,n) if (!pre[i]) dfs(i);
}
void mem(int n) {
Rep(i,n) G[i].clear(),G2[i].clear();
}
}S2;
class Max_flow //dinic+当前弧优化
{
public:
int n,t;
int q[MAXN];
ll weight[MAXM];
int edge[MAXM],Next[MAXM],Pre[MAXN],size;
void addedge(int u,int v,int w)
{
edge[++size]=v;
weight[size]=w;
Next[size]=Pre[u];
Pre[u]=size;
}
void addedge2(int u,int v,int w){addedge(u,v,w),addedge(v,u,0);}
bool b[MAXN];
ll d[MAXN];
bool SPFA(int s,int t)
{
MEMI(d)
MEM(b)
d[q[1]=s]=0;b[s]=1;
int head=1,tail=1;
while (head<=tail)
{
int now=q[head++];
Forp(now)
{
int &v=edge[p];
if (weight[p]&&!b[v])
{
d[v]=d[now]+1;
b[v]=1,q[++tail]=v;
}
}
}
return b[t];
}
int iter[MAXN];
int dfs(int x,ll f)
{
if (x==t) return f;
Forpiter(x)
{
int v=edge[p];
if (weight[p]&&d[x]<d[v])
{
int nowflow=dfs(v,min(weight[p],f));
if (nowflow)
{
weight[p]-=nowflow;
weight[p^1]+=nowflow;
return nowflow;
}
}
}
return 0;
}
ll max_flow(int s,int t)
{
(*this).t=t;
ll flow=0;
while(SPFA(s,t))
{
For(i,n) iter[i]=Pre[i];
ll f;
while (f=dfs(s,INF))
flow+=f;
}
return flow;
}
void mem(int n)
{
(*this).n=n;
size=1;
MEM(Pre)
}
void init(int n) {
For(i,n) {
Forp(i) {
int v=edge[p];
// cout<<i<<' '<<v<<' '<<weight[p]<<endl;
if (!weight[p]) {
// if (i<=n1&&v>n1&&v<=n1+m1) {
// ::b[i][v-n1]=1;
// // cout<<i<<' '<<v-n1<<endl;
// }
}
else S2.G[i-1].pb(v-1),S2.G2[i-1].pb(p);
}
}
}
}S;
struct {
int u,v;
}e[MAXM];
int main() {
int n,m,s,t;
n=read(),m=read(),s=read(),t=read();
S.mem(n);
For(i,m) {
int u=read(),v=read(),w=read();
S.addedge2(u,v,w);
e[i].u=u,e[i].v=v;
}
ll p=S.max_flow(s,t);
S.init(n);
S2.find_scc(n);
s--,t--;
For(i,m) {
e[i].u--,e[i].v--;
if (S.weight[i*2]) puts("0 0");
else if (S2.sccno[e[i].u]==S2.sccno[s] && S2.sccno[e[i].v]==S2.sccno[t]) puts("1 1");
else if (S2.sccno[e[i].u]!=S2.sccno[e[i].v]) puts("1 0");
else puts("0 0");
}
S2.mem(n);
}
return 0;
}