刚学网络流,随便写的,
没想到错误方法都能混80
Code
#include<bits/stdc++.h>
using namespace std;
int n,m,ss,t;
int e[3001][3001],s[20001],book[10001],ans,top,flag,mi;
void dfs(int x) {
if(x==t) {
s[++top]=t;
flag=1;
mi=99999999;
for(int i=1; i<top; i++) {
int x,y;
x=s[i];
y=s[i+1];
mi=min(mi,e[x][y]);
}
for(register int i=1; i<top; i++) {
int x,y;
x=s[i];
y=s[i+1];
e[x][y]-=mi;
e[y][x]+=mi;
}
ans+=mi;
return;
}
if(book[x]==1)
return;
book[x]=1;
s[++top]=x;
for(int i=1; i<=n; i++) {
if(e[x][i]>0) {
dfs(i);
}
}
top--;
return ;
}
int main() {
cin>>n>>m>>ss>>t;
// while(~scanf("%d %d %d %d",&n,&m,&s,&t)) {
for(register int i=1; i<=m; i++) {
int u,v;
cin>>u>>v;
e[u][v]=1;
e[v][u]=1 ;
}
while(1)
{
memset (book ,0,sizeof book);
top=0,flag=0;
dfs(ss);
if(flag==0)
break;
}
cout<<ans<<endl;
return 0;
// }
// return 0;
}