网络流之最大流Dinic算法模版

时间:2021-10-15 13:36:51
 /*
网络流之最大流Dinic算法模版
*/
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = ;
const int inf = 0x3f3f3f3f;
struct
{
int c,f;//c为边的容量,f为边的容量
}edge[maxn][maxn];
int dis[maxn];
int v,e;
bool bfs()//利用bfs进行分层处理,当汇点无法分层时得到最大流
{
memset(dis,,sizeof dis);
queue<int> q;
q.push();
dis[] = ;
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = ; i <= v; ++i)
if(!dis[i] && edge[u][i].c > edge[u][i].f)
{dis[i] = dis[u] + ;q.push(i);}
}
return dis[v] != ;
}
int dfs(int u,int c)//增广
{
if(u == v) return c;
int temp = c;
for(int i = ; i <= v && temp; ++i)
{
if(dis[i] != dis[u] + || edge[u][i].c <= edge[u][i].f) continue;
int t = dfs(i,min(temp,edge[u][i].c - edge[u][i].f));
edge[u][i].f += t; edge[i][u].f -= t; temp -= t;
}
return c - temp;
}
int dinic()
{
int ans = ;
while(bfs())
while(int t = dfs(,inf))
ans += t;
return ans;
}
int main()
{
while(~scanf("%d%d",&e,&v))
{
memset(edge,,sizeof edge);
while(e--)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
edge[x][y].c += z;
}
int ans = dinic();
printf("%d\n",ans);
}
return ;
}