初始网络流

题目链接：https://cn.vjudge.net/problem/HDU-1532

AC代码：

#include<iostream>
#include<string>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<stdio.h>
#include<queue>
using namespace std;
# define maxn 200+10
# define inf 0x3f3f3f3f
# define ll long long
int Map[maxn][maxn];
int pre[maxn];
int vis[maxn];
int n,m;
bool bfs(int s,int t){
memset(vis,0,sizeof(vis));
queue<int>q;
vis[s]=1;
pre[s]=s;
q.push(s);
while(!q.empty())
{
int top=q.front();
q.pop();
for(int i=1;i<=m;i++){
if(Map[top][i]&&!vis[i]){
pre[i]=top;
vis[i]=1;
if(i==t)return true;
q.push(i);
}
}
}
return false;
}
int Find(int s,int t){
int ans=0;
while(bfs(s,t)){//寻找增广路的过程。
int minn=inf;
for(int i=t;i!=s;i=pre[i]){
minn=min(minn,Map[pre[i]][i]);//寻找最小流，不会出现0的过程，
}
for(int i=t;i!=s;i=pre[i]){
Map[pre[i]][i]-=minn;//正向减权值
Map[i][pre[i]]+=minn;//反向加权值
}
ans+=minn;
}
return ans;
}
int main(){
while(~scanf("%d%d",&n,&m)){
memset(Map,0,sizeof(Map));
for(int i=1;i<=n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
Map[u][v]+=w;//建图的过程
}
int ans=Find(1,m);
printf("%d
",ans);
}
return 0;
}