一看题目就是最小割
但是这道题需要几个~~神奇的~~结论
**1、残余网络中有剩余流量的边一定不在最小割方案中**
**2、残余网络中一条边的两个端点（满足1）还能相互到达，则这条边不在最小割方案中**
wgl：一条边的两个端点能相互到达，则它们在割后的同一集合中，所以连接它们的边
肯定不在最小割方案中啊！
**3、残余网络中一条边（满足1）的两个端点分别和s，t在同一集合中，则这条边在最小割方案中。**
wgl:你不割这条边，最小割肯定得改变！
所以**dinic之后用tarjan判断连通性即可**
```cpp
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define reg register
using namespace std;
const int N=4005,inf=1e8;
struct edge
{
int to,from,nxt,dis;
}edge[120005];
int n,m,s,t,num=1,head[N],dep[N],dfn[N];
int low[N],stack[N],top,cnt,ans,belong[N];
bool exist[N];
inline int read()
{
int x=0,w=1;
char c=getchar();
while (!isdigit(c)&&c!='-') c=getchar();
if (c=='-') c=getchar(),w=-1;
while (isdigit(c))
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*w;
}
inline void add_edge(int from,int to,int dis)
{
edge[++num].nxt=head[from];
edge[num].to=to;
edge[num].from=from;
edge[num].dis=dis;
head[from]=num;
}
inline bool bfs()
{
queue<int>q;
memset(dep,0,sizeof(dep));
q.push(s); dep[s]=1;
while (!q.empty())
{
int u=q.front(); q.pop();
for (reg int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].to,d=edge[i].dis;
if (!dep[v]&&d)
{
dep[v]=dep[u]+1; q.push(v);
}
}
}
return dep[t];
}
int dfs(int k,int dis)
{
if (k==t||!dis) return dis; int sum=0;
for (reg int i=head[k];i;i=edge[i].nxt)
{
int v=edge[i].to,d=edge[i].dis;
if (dep[v]==dep[k]+1&&d)
{
int temp=dfs(v,min(d,dis));
if (temp>0)
{
edge[i].dis-=temp;
edge[i^1].dis+=temp;
sum+=temp; dis-=temp;
if (!dis) return sum;
}
}
}
if (!sum) dep[k]=-1;
return sum;
}
inline int dinic()
{
while (bfs()) dfs(s,inf);
}
void tarjan(int k)
{
int temp;
dfn[k]=low[k]=++cnt;
stack[++top]=k; exist[k]=1;
for (reg int i=head[k];i;i=edge[i].nxt)
{
if (!edge[i].dis) continue;
int v=edge[i].to;
if (!dfn[v])
{
tarjan(v);
low[k]=min(low[k],low[v]);
}
else if (exist[v])
low[k]=min(low[k],dfn[v]);
}
if (dfn[k]==low[k])
{
++ans;
do
{
temp=stack[top--];
exist[temp]=0;
belong[temp]=ans;
}while (temp!=k);
}
}
int main()
{
n=read(),m=read(),s=read(),t=read();
for (reg int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
add_edge(x,y,z);
add_edge(y,x,0);
}
dinic();
for (reg int i=1;i<=n;i++)
if (!dfn[i]) tarjan(i);
for (reg int i=2;i<=num;i+=2)
{
int u=edge[i].from,v=edge[i].to;
if (edge[i].dis)
{
printf("0 0\n"); continue;
}
if (belong[u]==belong[v]) printf("0 ");
else printf("1 ");
if (belong[u]==belong[s]&&belong[v]==belong[t])
printf("1\n"); else printf("0\n");
}
return 0;
}
```