结论:

满足条件一:当一条边的起点和终点不在 残量网络的 一个强联通分量中。且满流。

满足条件二:当一条边的起点和终点分别在 S 和 T 的强联通分量中。且满流。、

网上题解很多的。

 #include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 2147483647
#define MAXN 4011
#define MAXM 120101
int v[MAXM],cap[MAXM],en,first[MAXN],next[MAXM];
int d[MAXN],cur[MAXN],cmp[MAXN],sum;
bool vis[MAXN];
queue<int>q;
vector<int>vs;
int n,m,S,T,A,B,C;
void Init_Dinic(){memset(first,-,sizeof(first)); en=;}
void AddEdge(const int &U,const int &V,const int &W)
{v[en]=V; cap[en]=W; next[en]=first[U]; first[U]=en++;
v[en]=U; next[en]=first[V]; first[V]=en++;}
bool bfs()
{
memset(d,-,sizeof(d)); q.push(S); d[S]=;
while(!q.empty())
{
int U=q.front(); q.pop();
for(int i=first[U];i!=-;i=next[i])
if(d[v[i]]==- && cap[i])
{
d[v[i]]=d[U]+;
q.push(v[i]);
}
}
return d[T]!=-;
}
int dfs(int U,int a)
{
if(U==T || !a) return a;
int Flow=,f;
for(int &i=cur[U];i!=-;i=next[i])
if(d[U]+==d[v[i]] && (f=dfs(v[i],min(a,cap[i]))))
{
cap[i]-=f; cap[i^]+=f;
Flow+=f; a-=f; if(!a) break;
}
if(!Flow) d[U]=-;
return Flow;
}
void max_flow()
{
while(bfs())
{
memcpy(cur,first,(n+)*sizeof(int));
while(dfs(S,INF));
}
}
void dfs(int U)
{
vis[U]=;
for(int i=first[U];i!=-;i=next[i]) if(cap[i]&&(!vis[v[i]])) dfs(v[i]);
vs.push_back(U);
}
void dfs2(int U)
{
cmp[U]=sum;
for(int i=first[U];i!=-;i=next[i]) if(cap[i^]&&(!cmp[v[i]])) dfs2(v[i]);
}
void scc()
{
for(int i=;i<=n;i++) if(!vis[i]) dfs(i);
vector<int>::iterator it=vs.end(); --it;
for(;;--it)
{
if(!cmp[*it]) {++sum; dfs2(*it);}
if(it==vs.begin()) break;
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&S,&T); Init_Dinic();
for(;m;--m)
{
scanf("%d%d%d",&A,&B,&C);
AddEdge(A,B,C);
}
max_flow(); scc();
for(int i=;i<en;i+=)
printf("%d %d\n",(!cap[i])&&cmp[v[i+]]!=cmp[v[i]],(!cap[i])&&cmp[v[i+]]==cmp[S]&&cmp[v[i]]==cmp[T]);
return ;
}

最新文章

  1. checkbox的全选与反选
  2. arcgis for flex展示GIS基本功能
  3. 设定自动获得DNS服务器地址
  4. Linux下多进程编程之exec函数语法及使用实例
  5. Poisson回归模型
  6. iOS学习之六种传值方式
  7. iOS:UIView的block函数实现转场动画---单视图
  8. spring读取prperties配置文件(1)
  9. novnc ignoring socket not reay
  10. java web实现 忘记密码(找回密码)功能及代码
  11. elike.python.function()
  12. Python2中while 1比while True更快
  13. (转)CentOS 7.0关闭默认防火墙启用iptables防火墙
  14. iOS上new Date异常解决办法
  15. MongoDB系列五(地理空间索引与查询).
  16. BZOJ 3817 Sum
  17. 优化算法系列-遗传算法(3)——NSGAII学习网址
  18. C#基础加强(6)之引用相等与运算符重载
  19. excel追加数据
  20. 20155311《网络对抗》Web安全基础实践

热门文章

  1. More on understanding sort_buffer_size
  2. Codeforces 937.B Vile Grasshoppers
  3. IDEA 用maven创建web项目编译时不能发布resources中的文件
  4. 更改win10和mint双系统默认启动顺序
  5. Java之戳中痛点 - (2)取余用偶判断,不要用奇判断
  6. CSS去掉 a 标签点击后出现的虚线框
  7. ES6学习笔记(二)——数组的扩展
  8. SDK登录cognos
  9. hdu 2112 HDU Today (最短路)
  10. 打印python的堆栈stack