~~不要在意EK的复杂度,反正能过就行了~~
by Sai0511 @ 2018-10-04 18:19:51
萌新网络流,可啪。。。
又是**初学OI的都是怪物系列**
by 土田共戈 @ 2018-10-04 18:22:04
@[Sai_0511](/space/show?uid=114320) e
by zzqDeco @ 2018-10-04 18:24:28
@[Sai_0511](/space/show?uid=114320) 好强
by zzqDeco @ 2018-10-04 18:25:42
@[zzqzzqzzq](/space/show?uid=62573) Orz话说我错在哪了QAQ
by Sai0511 @ 2018-10-04 18:29:06
@[Sai_0511](/space/show?uid=114320) 不知道,我还没学网络流(自己只打了一道题)
by zzqDeco @ 2018-10-04 18:32:00
@[Sai_0511](/space/show?uid=114320)
%%%
by Smile_Cindy @ 2018-10-04 18:32:55
@[Sai_0511](/space/show?uid=114320) 果然人如其像,像不虚传(头像)
by SofanHe @ 2018-10-04 18:36:36
// luogu-judger-enable-o2
#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,ans,f[10001],r[10001][2],st,en,x,y,z;
struct data{
int a,b,c;
data(int a,int b,int c){
this->a=a;
this->b=b;
this->c=c;
}
};
vector<data> v;
vector<int> u[10001];
void bfs(){
queue<int> q;
int k=0;
while(1){
for(int i=1;i<=n;i++)f[i]=0;
f[st]=1000000000;
q.push(st);
while(!q.empty()){
x=q.front();
q.pop();
for(int i=0;i<u[x].size();i++){
y=u[x][i];
data d=v[y];
if(f[d.b]==0&&d.c){
f[d.b]=min(f[x],d.c);
r[d.b][0]=x;
r[d.b][1]=y;
q.push(d.b);
}
}
}
if(f[en]==0)break;
for(int i=en;i!=st;i=r[i][0]){
v[r[i][1]].c-=f[en];
v[r[i][1]^1].c+=f[en];
}
ans+=f[en];
}
return;
}
int main(){
scanf("%d %d %d %d",&n,&m,&st,&en);
for(int i=1;i<=m;i++){
scanf("%d %d %d",&x,&y,&z);
v.push_back(data(x,y,z));
u[x].push_back(v.size()-1);
v.push_back(data(y,x,0));
u[y].push_back(v.size()-1);
}
bfs();
printf("%d",ans);
}
by suyiheng @ 2018-10-04 18:43:41
发个我A了的代码
by suyiheng @ 2018-10-04 18:44:28