首先是网络流及最小费用最大流的两种最基础算法
这两种网络流算法的思想核心都是寻找增广路+沿增广路扩展新流 首先是Dinic 算法 使用bfs寻找增广路，记录增广路中节点层数， 而在dfs中沿着层数+1的方向不断递推 直到无法再找到新的增广路为止代码
#include#include #include #include #include #include #include using namespace std;#define N 105#define next nicoint head[N],to[N*N*2],next[N*N*2],dis[N*N*2],tot=1,d[N],s=0,t,n,m;void add(int x,int y, int z){ to[++tot]=y; dis[tot]=z; next[tot]=head[x]; head[x]=tot;}int bfs(){ memset(d,0,sizeof(d)); queue q; d[s]=1; q.push(s); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x]; i; i = next[i]) { int des = to[i]; if(dis[i]&&!d[des]) { d[des]=d[x]+1; q.push(des); } } } return d[t];}int dfs(int x,int v){ if(x==t||v==0)return v; int ans = 0; for(int i = head[x]; i ; i = next[i]) { int des = to[i]; if(d[des]==d[x]+1) { int f = dfs(des,min(dis[i],v)); v -= f; dis[i]-=f; dis[i^1]+=f; ans += f; } } return ans;}int dinic(){ int ans = 0; while(bfs()) { ans +=dfs(s,0x7f7f7f7f); } return ans ;}
接下来是最小费用最大流
存图时注意反向边的费用是正向边的相反数同dinic算法的区别在于一次只有一条增广路，且这条增广路是费用最短路
可以使用spfa来寻找增广路 然而众所周知 spfa 它死了
所以我采用了dijkstra
但是dijkstra不能处理负边权，怎么办？ 一种方法是每条边权加上一个足够大的数最后再减去 但是有着溢出的风险！ 另一种方法 我们采用数组h[i]表示上一次增广路时的最短路 w[i][j]表示连接i,j边的权值 那么有h[i]+w[i][j]>=h[j] 所以h[i]-h[j]+w[i][j]>=0 记保存当前最短路的数组为f[i] 而我们可以证明最后求出的最短路长度即为f[i]-h[i] 最后为了维护h 只需要每个h[i]+=f[i] 代码#include#include #include #include #include #include #define N 5003#define next nicousing namespace std;int head[N],to[N*20],v[N*20],cost[N*20],from[N],flow[N],next[N*20],f[N],path[N],tot=1,h[N],n,m;int sumflow,sumcost;int s,t;void add(int x,int y,int a,int b){ to[++tot]=y; cost[tot]=a; v[tot]=b; next[tot]=head[x]; head[x]=tot;}struct dat{ int val,p; bool operator < (const dat &b )const { return val > b.val; }}buf;int dijkstra(){ memset(f,0x7f,sizeof(f)); memset(flow,0x7f,sizeof(flow)); memset(from,0,sizeof(from)); memset(path,0,sizeof(path)); int inf = f[0]; f[s]=0; priority_queue p; p.push(dat{ 0,s}); while(!p.empty()) { dat t = p.top(); p.pop(); int x = t.p; if(t.val==f[x]) for(int i = head[t.p];i;i=next[i]) { int des = to[i]; if(v[i]&&f[x]+cost[i]+h[x]-h[des]