上下界网络流的一些理解

周源论文中的二分法求解虽用途广,但效率不高,容易被卡时间,所以非二分的扩流法和缩流法比较好
注意点:设下界为low,上界为high,残量网络中该边残余容量c,则最后该边的流量=low+(high-low-c)=high-c;亦即上界-残量
1.有源汇上下界最大流
(1)加弧,转变成无源汇可行流问题
(2)添加附加源汇ss、tt。求出是否存在可行流。
(3)现在已经有了可行流,去掉。从s到t求最大流,(网上说要去掉附加源汇ss,tt,其实我感觉不用去,因为ss和tt间没边,所以必要弧不可能退流,个人理解,正确性有待检验)
2.有源汇上下界最小流
(1)和最大流一样构造附加网络(但不添加
(2)求ss到tt的最大流ans1
(3)加,求ss到tt的最大流ans2
(4)如果ans1+ans2等于附加网络的满流流量(以ss、tt为源汇),则有解,且的流量就是最小流,否则无解
这个方法无bug,但我还没完全理解
还有一个有bug的方法:和求解最大流基本一样,只是最后一步是从t到s求最大流,也就是缩流,但是存在bug:可能出现缩流的量比可行流还大,也就是最终最小流为负,其实这种情况意味着原网络中间出现环流,也就是源点s不必产生流量也能符合要求,此时最小流为0

hdoj3046

想不到思路,,只能百度,对于一个刚学网络流的人来说建图感觉很难。
思路:附加源点和汇点,将源点和map[i][j]=1的点连有向边,容量无限,将map[i][j]=2的点和汇点连有向边,容量无限。矩阵的每个格都是图的一个顶点。将矩阵中相邻的格连有向边,容量为1(两个格相邻对应了两条有向边,a->b,b->a;加上回退边,总共四条有向边)
这样题目就变成了:最少去掉几条边,使该图不连通(显然最少去边方案肯定会把为1和为2的点分到两个不同的子图里去,用反证。。),也就是求最小割(因为每条有向边cap=1,最小割边最少,且能使图不连通,而且最小割的边满流,所以最后最大流多少,最小割就有多少条边(最大流=最小割各边cap之和))
第一次最大流建图,写得详细些^_^

dinic算法

cur数组:对于每次bfs建立的层次图,cur[x]用于记录上一次dfs过程中选择的x的出边在edge数组中的下标(这样,本次从x点出发继续dfs时就会从x的静态链表的下标为cur[x]的边开始继续dfs,这样可以避免重复,个人理解作用有点像visit数组。好吧,比较难叙述,多画画图就明白了)

最小费用最大流(邻接矩阵)

//假设没有反向边,平行边
//思想:用bellman-ford找增广路。只要初始流是该流量下的最小费用可行流,每次增广后的新流都是新流量下的最小费用流。
//费用可正可负
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define maxn 1010
#define inf 1000000000
using namespace std;
int cap[maxn][maxn],flow[maxn][maxn],cost[maxn][maxn];
int p[maxn];
int n;
typedef struct Ans{
	int c;
	int f;
}ANS;
int min(int a,int b)
{
	return a<b?a:b;
}
ANS mincost_maxflow(int s,int t)
{
	int i;
	queue<int> q;
	int d[maxn];
	memset(flow,0,sizeof(flow));
	int c=0;
	int f=0;
	while(1)
	{
		bool inq[maxn];
		memset(inq,0,sizeof(inq));
		for(i=1;i<=n;i++)
		{
			d[i]=inf;
			p[i]=-1;
		}
		d[s]=0;
		memset(inq,0,sizeof(inq));
		q.push(s);
		inq[s]=1;
		while(!q.empty())//用bellman-ford找增广路,这样每次找到的增广路都是s到t的最短路,也就是费用最小的增广路;所以可以保证在新流量下,费用最小
		{
			int u=q.front();
			q.pop();
			inq[u]=0;
			for(int v=1;v<=n;v++)
			{
				if(cap[u][v]>flow[u][v] && d[v]>d[u]+cost[u][v])
				{
					d[v]=d[u]+cost[u][v];
					p[v]=u;
					if(!inq[v])
					{
						q.push(v);
						inq[v]=1;
					}
				}
			}
		}

		if(d[t]==inf) break;
		int a=inf;
		int u;
		for(u=t;u!=s;u=p[u])
			a=min(a,cap[p[u]][u]-flow[p[u]][u]);
		for(u=t;u!=s;u=p[u])
		{
			flow[p[u]][u]+=a;
			flow[p[u]][u]-=a;
		}
		c+=a*d[t];
		f+=a;
	}
	ANS ans;
	ans.f=f;
	ans.c=c;
	return ans;
}
int main()
{
//残量网络中存在边cap[u][v]>0,则cap[v][u]=0,cost[v][u]=-cost[u][v];	
//system("pause");
return 0;
}

ek算法的另一种写法

刘汝佳《算法入门经典》里的ek算法写法
这种写法的好处是当求出最大流后,最小割[S,T]也就求出来了。算法结束后,如果a[u]大于0,那么说明在最后的残量网络中s到u有路可达,所以点u在S集合中,反之在T集合中。
可以发现,最小割的正向割边都是满流量的,也就是曾经增广过程中的“瓶颈边”。

最大流EK算法模板

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
using namespace std;
const int MAXN=110;
int map[MAXN][MAXN],n,p[MAXN];
int min(int a,int b)
{
	return a<b?a:b;
}
bool ek_bfs(int start,int end)
{
	int i;
	queue<int> q;
	bool visit[MAXN];
	memset(visit,0,sizeof(visit));
	memset(p,-1,sizeof(p));
	q.push(start);
	visit[start]=1;
	while(!q.empty())
	{
		int e=q.front();
		if(e==end)
			return true;
		q.pop();
		for(i=1;i<=n;i++)
		{
			if(map[e][i] && !visit[i])
			{
				visit[i]=1;
				p[i]=e;
				q.push(i);
			}
		}
	}
	return false;
}
int ek(int start,int end)
{
	int u,flow=0,mn;
	while(ek_bfs(start,end))
	{
		mn=INT_MAX;
		u=end;
		while(p[u]!=-1)
		{
			mn=min(mn,map[p[u]][u]);
			u=p[u];
		}
		flow+=mn;
		u=end;
		while(p[u]!=-1)
		{
			map[p[u]][u]-=mn;
			map[u][p[u]]+=mn;
			u=p[u];
		}
	}
	return flow;
}
int main()
{
	
//system("pause");
return 0;
}