网络流算法集合 EK dinic 最小费用最大流 (Dijkstra实现)

本文主要是介绍网络流算法集合 EK dinic 最小费用最大流 (Dijkstra实现)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

终于快把网络流的模板写完了,先贴几个,存边用前向星实现，既保证了速度又免去了写链表的麻烦，代码绝对是你能找到的代码中最精简的

//EK
#include<stdio.h>
#include<iostream>
using namespace std;
#include<memory.h>
#define MAXN 300
#define MAXFLOW 2000000000
int n,s,t,m,flow[MAXN+1][MAXN+1],map[MAXN+1][MAXN+1],pre[MAXN+1];
void init()
{
  int i,a,b,c;
  memset(map,0,sizeof(map));
  memset(flow,0,sizeof(flow));
  memset(pre,0,sizeof(pre));
  cin>>n>>s>>t>>m;
  for(i=1;i<=m;i++)
  {
 cin>>a>>b>>c;
 map[a][0]++;
 map[a][map[a][0]]=b;
        map[b][0]++;
        map[b][map[b][0]]=a;
        flow[a][b]+=c;//对于重边的存在,推荐用+=
  }
}
int bfs()
{
  int i,tt[MAXN+1],start,finish,chk[MAXN+1],k;
  memset(tt,0,sizeof(tt));
  memset(chk,0,sizeof(chk));
  start=1;finish=1;tt[1]=s;
  while(start<=finish)
  {
    for(i=1;i<=map[tt[start]][0];i++)
   if ((!chk[map[tt[start]][i]])&&(flow[tt[start]][map[tt[start]][i]]))
   {
    k=map[tt[start]][i];
    finish++;
    tt[finish]=k;
    chk[k]=1;
    pre[k]=tt[start];
    if(k==t) return 1;
   }
  start++;
  }
 return 0;

}
int min(int a,int b)
{
  if (a<b) return a;
    else return b;
}
int main()
{
  int ans,k

这篇关于网络流算法集合 EK dinic 最小费用最大流 (Dijkstra实现)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---