YBT_mail @ 2020-08-27 08:41:49
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
int n,m,s,t;
vector <Edge> edges;
vector <int> G[10003];
int d[1003],cur[1003],mm;
bool vis[1003];
void add(int from,int to,int cap){
edges.push_back(Edge(from,to,cap,0));
edges.push_back(Edge(to,from,0,0));
mm=edges.size();
G[from].push_back(mm-2);
G[to].push_back(mm-1);
}
bool bfs(){
memset(vis,0,sizeof(vis));
queue<int> Q;
Q.push(s);
d[s]=0;
vis[s]=1;
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i=0;i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow){
vis[e.to]=1;
d[e.to]=d[x]+1;
Q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x,int a){
if(x==t||a==0) return a;
int flow=0,f;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
e.flow+=f;
edges[G[x][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0) break;
}
}
return flow;
}
int Maxflow(int ss,int tt){
s=ss,t=tt;
int flow=0;
while(bfs()){
memset(cur,0,sizeof(cur));
flow+=dfs(s,100000000);
}
return flow;
}
int main(){
int ss,tt,x,y,c;
cin>>n>>m>>ss>>tt;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&c);
add(x,y,c);
}
cout<<Maxflow(ss,tt);
return 0;
}
by YBT_mail @ 2020-08-27 08:45:04
我贴的是第一次交的代码,有些地方还有漏洞,改过了还是没过。太蒻了
by 灵茶山艾府 @ 2020-08-27 08:53:13
flow+=dfs(s,100000000)
这个传小了吧,你看看数据范围
by Prean @ 2020-08-27 08:58:36
不开 ____ 见祖宗
by hanyuchen2019 @ 2020-08-27 09:34:10
不开 ____ 见祖宗
by YBT_mail @ 2020-09-17 15:27:19
调到我眼瞎
by YBT_mail @ 2020-09-17 15:30:09
不开long long见祖宗
by YBT_mail @ 2020-09-17 15:37:06
多谢