王奕霏 @ 2020-09-19 15:31:14
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int n, m, sorce, target, cnt;
int heads[10010], level[10010];
struct Node{
int from;
int to;
int capacity;
int next;
};
Node edges[100010];
void add(int f, int t, int c){
edges[cnt].from=f;
edges[cnt].to=t;
edges[cnt].capacity=c;
edges[cnt].next=heads[f];
heads[f]=cnt;
swap(f, t); cnt++;
edges[cnt].from=f;
edges[cnt].to=t;
edges[cnt].capacity=0;
edges[cnt].next=heads[f];
heads[f]=cnt; cnt++;
return;
}
bool bfs(){
memset(level, -1, sizeof(level));
queue<int> q;
q.push(sorce);
level[sorce]=0;
while(!q.empty()){
int top=q.front(); q.pop();
// cout << top << endl;
if(top==target) return true;
for(int i=heads[top];i!=-1;i=edges[i].next){
int t=edges[i].to;
int c=edges[i].capacity;
// printf("edges[%d]: from=%d, to=%d, capacity=%d, next=%d\n", i, edges[i].from, t, c, edges[i].next);
if(level[t]==-1 && c>0){
level[t]=level[top]+1;
q.push(t);
}
}
}
return false;
}
int dfs(int u, int mx){
// cout << u << endl;
if(u==target || mx<=0) return mx;
int sum=0;
for(int i=heads[u];i!=-1;i=edges[i].next){
int t=edges[i].to;
int c=edges[i].capacity;
// cout << t << endl;
if(level[t]==level[u]+1 && c>0){
int ans=dfs(t, min(mx-sum, c));
sum+=ans;
edges[i].capacity-=ans;
edges[i^1].capacity+=ans;
if(sum==mx) return mx;
}
}
return sum;
}
int dinic(){
int ans=0;
while(bfs()){
// printf("1 ");
ans+=dfs(sorce, 0x3f3f3f3f);
// printf("\n\n\n\n\n\n");
}
// printf("\n");
return ans;
}
int main(){
scanf("%d%d%d%d", &n, &m, &sorce, &target);
memset(heads, -1, sizeof(heads));
for(int i=0;i<m;i++){
int f, t, c;
scanf("%d%d%d", &f, &t, &c);
add(f, t, c);
}
printf("%d\n", dinic());
return 0;
}
by metaphysis @ 2020-09-19 18:13:09
@王奕霏
读题时对数据范围要特别注意:
4 4 1 4
1 2 2147483647
1 3 2147483647
2 4 2147483647
3 4 2147483647
您的输出:
-2
正确输出:
4294967294
by metaphysis @ 2020-09-19 18:15:47
@王奕霏
您先把这个问题修正先看能不能AC,如果有问题的话,我再帮您看看。
by 王奕霏 @ 2020-10-09 17:10:50
@metaphysis 好的好的 非常感谢