#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct Node{
int from;
int to;
int capacity;
int next;
};
int heads[10010], target, sorce, level[10010], num_dian, num_bian;
Node edges[200100];
int in(int from, int to, int capacity, int i){
edges[i].from=from;
edges[i].to=to;
edges[i].capacity=capacity;
edges[i].next=heads[from];
heads[from]=i;
edges[i+1].from=to;
edges[i+1].to=from;
edges[i+1].capacity=0;
edges[i+1].next=heads[to];
heads[to]=i+1;
}
bool bfs(){
queue<int> q;
memset(level, -1, sizeof(level));
q.push(sorce);
level[sorce]=0;
while(!q.empty()){
int f=q.front();
if(f==target){
return true;
}
q.pop();
for(int i=heads[f];i!=-1;i=edges[i].next){
if(edges[i].capacity>0 && level[i]==-1){
q.push(i);
level[i]=level[f]+1;
}
}
}
return false;
}
int dfs(int from, int mx){
int ans=0;
if(from==target || mx<=0){
return 0;
}
for(int i=heads[from];i!=-1;i=edges[i].next){
if(level[i]==level[from]+1 && edges[from].capacity>0){
int an=dfs(i, min(edges[i].capacity, mx-ans));
ans+=an;
edges[i].capacity-=an;
edges[i^1].capacity+=an;
if(ans==mx){
return ans;
}
}
}
return ans;
}
int dinic(){
int ans=0;
while(bfs){
ans+=dfs(sorce, 0x3F3F3F3F);
}
return ans;
}
int main(){
cin >> num_dian >> num_bian >> sorce >> target;
memset(heads, -1, sizeof(heads));
for(int i=0;i<num_bian*2;i+=2){
int from, to, weight;
cin >> from >> to >> weight;
in(from, to, weight, i);
}
cout << dinic();
}
by 王奕霏 @ 2018-06-13 14:26:59
bool bfs(){
queue<int> q;
memset(level, -1, sizeof(level));
q.push(sorce);
level[sorce]=0;
while(!q.empty()){
int f=q.front();
if(f==target){
return true;
}
q.pop();
for(int i=heads[f];i!=-1;i=edges[i].next){
if(edges[i].capacity>0 && level[i]==-1){
q.push(i);
level[i]=level[f]+1;
}
}
}
return false;
}
by 王奕霏 @ 2018-06-13 14:28:50
```
bool bfs(){
queue<int> q;
memset(level, -1, sizeof(level));
q.push(sorce);
level[sorce]=0;
while(!q.empty()){
int f=q.front();
if(f==target){
return true;
}
q.pop();
for(int i=heads[f];i!=-1;i=edges[i].next){
if(edges[i].capacity>0 && level[i]==-1){
q.push(i);
level[i]=level[f]+1;
}
}
}
return false;
}
//有毒把。。
```
by moye到碗里来 @ 2018-06-13 15:00:47
用markdown a
by moye到碗里来 @ 2018-06-13 15:01:19
恩恩谢！！
by 王奕霏 @ 2018-06-13 15:34:25
```
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct Node{
int from;
int to;
int capacity;
int next;
};
int heads[10010], target, sorce, level[10010], num_dian, num_bian;
Node edges[200100];
int in(int from, int to, int capacity, int i){
edges[i].from=from;
edges[i].to=to;
edges[i].capacity=capacity;
edges[i].next=heads[from];
heads[from]=i;
edges[i+1].from=to;
edges[i+1].to=from;
edges[i+1].capacity=0;
edges[i+1].next=heads[to];
heads[to]=i+1;
}
bool bfs(){
cout << "a1";
queue<int> q;
memset(level, -1, sizeof(level));
q.push(sorce);
level[sorce]=0;
while(!q.empty()){
int f=q.front();
if(f==target){
cout << "true" << endl;
return true;
}
cout << "a" << endl;
q.pop();
for(int i=heads[f];i!=-1;i=edges[i].next){
if(edges[i].capacity>0 && level[i]==-1){
q.push(i);
level[i]=level[f]+1;
}
}
}
return false;
}
int dfs(int from, int mx){
int ans=0;
if(from==target || mx<=0){
return 0;
}
for(int i=heads[from];i!=-1;i=edges[i].next){
if(level[i]==level[from]+1 && edges[from].capacity>0){
int an=dfs(i, min(edges[i].capacity, mx-ans));
ans+=an;
edges[i].capacity-=an;
edges[i^1].capacity+=an;
if(ans==mx){
return ans;
}
}
}
return ans;
}
int dinic(){
int ans=0;
cout << "b";
while(bfs){
cout << "a2";
ans+=dfs(sorce, 0x3F3F3F3F);
}
return ans;
}
int main(){
cin >> num_dian >> num_bian >> sorce >> target;
memset(heads, -1, sizeof(heads));
for(int i=0;i<num_bian*2;i+=2){
int from, to, weight;
cin >> from >> to >> weight;
in(from, to, weight, i);
}
cout << dinic();
}
```
by 王奕霏 @ 2018-06-13 15:36:07
哪位大佬看看
by 王奕霏 @ 2018-06-13 15:36:21
@[王奕霏](/space/show?uid=42479) 你这bfs并不是十分清晰啊……
我的bfs是这样的（感觉自己的清晰了不少）
```cpp
bool bfs()
{
memset(vis,false,sizeof(vis));
queue<int>Q;
Q.push(s);
dis[s]=0,vis[s]=true;
while(!Q.empty())
{
int head=Q.front();
Q.pop();
for(int i=0;i<G[head].size();i++)
{
node& e=E[G[head][i]];
if( !vis[e.to] && e.cap>e.flow )
{
vis[e.to]=true;
dis[e.to]=dis[head]+1;
Q.push(e.to);
}
}
}
return vis[t];
}
```
by info___tion @ 2018-07-06 09:40:57
@[王奕霏](/space/show?uid=42479) 诶，好像看出来了，你的bfs在加入节点的时候为什么只是$\color{blue}push(i)$呢？（不是应该$\color{blue}push(i.to)$ 吗？）
by info___tion @ 2018-07-06 09:42:54
@[王奕霏](/space/show?uid=42479) 你只$\color{blue}push(i)$的话不死循环才怪（反正来来去去都是同一条边）
by info___tion @ 2018-07-06 09:44:37