用c++代码写一个dinic算法
时间: 2023-03-07 07:01:24 浏览: 153
#include<stdio.h>
int max_flow(int n,int s,int t,int cap[][],int flow[][])
{
int pre[n],que[n],d[n],p,q,t,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
flow[i][j]=0;
while(true)
{
for(i=0;i<n;i++)
pre[i]=-1;
pre[s]=s;
d[s]=INF;
p=q=0;
que[q++]=s;
while(p<q)
{
i=que[p++];
for(j=0;j<n;j++)
{
if(pre[j]==-1&&cap[i][j]>flow[i][j])
{
pre[j]=i;
d[j]=min(d[i],cap[i][j]-flow[i][j]);
if(j==t)
break;
que[q++]=j;
}
}
if(pre[t]!=-1)
break;
}
if(pre[t]==-1)
break;
for(i=t;i!=s;i=pre[i])
{
flow[pre[i]][i]+=d[t];
flow[i][pre[i]]-=d[t];
}
}
int sum=0;
for(i=0;i<n;i++)
sum+=flow[s][i];
return sum;
}
阅读全文