如题,本蒟蒻最近在学网络流算法,所以虽然这题有更优的解法我还是比较希望能练习一下网络流算法的。这个算法是根据自己看的一些理论概念自己写的,但是貌似出了问题,个人感觉已经没什么问题了。。。求求神犇们帮忙指正一下!!
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
struct eee{
int next;
int to;
int w;
}edge[maxn<<1];
int r,n,cnt=1,root[maxn],fa[maxn],dest[maxn];
stack<int>path;
inline void add(int x,int y,int w){
edge[++cnt]={root[x],y,w};
root[x]=cnt;
}
void dfs(int u){
for(int i=root[u];i;i=edge[i].next){
int to=edge[i].to;
if(fa[u]==to)continue;
fa[to]=u;
//edge[i^1].w=0;
dfs(to);
}
if(!edge[root[u]].next&&u!=r){
dest[u]=1;
}
}
int find_path(int now,int from,int flow){
// printf("now=%d from=%d flow=%d\n",now,from,flow);
// printf("%d\n",dest[now]);
if(dest[now])return flow;
int qw=0;
for(int i=root[now];i;i=edge[i].next){
int to=edge[i].to,w=edge[i].w;
//printf("to is %d w is %d\n",to,w);
if(to==from)continue;
if(w==0)continue;
path.push(i);
qw=find_path(to,now,min(flow,w));
break;
}
return qw;
}
void maxflow(){
int ans=0;
while(1){
int l=find_path(r,0,0x7fffffff);
if(l!=0&&l!=0x7fffffff){
ans+=l;
while(path.size()){
int e=path.top();
path.pop();
edge[e].w-=l;
edge[e^1].w+=l;
}
}
else{
break;
}
}
printf("%d\n",ans);
}