网络最大流、二分图最大匹配、POJ2536

Filed in: 数据结构与算法 Add comments

通常我们把一个有向无环图边上的权值看做两个节点之间的距离，在这个模型下的问题有各种最短路问题。如果将边上的权值不看做距离而看做两点间的容量（比如两个城市之间一天的运输能力），这样的有向无环图就叫做流网络，对应的问题就是求最大流——单位时间内通过网络的最大容量（比如工厂所在城市一天最多可以生产多少才能全部经过一个流网络运到仓库所在城市而不造成中途的淤积）。

流网络只有一个源点和一个汇点。关于定义就不说了，算法导论上很清楚。有一点要说的是，如果一个流网络有多个源点和多个汇点，可以通过增加一个到所有现有源点的容量都无穷的超级源点和一个所有汇点到其容量都无穷的超级汇点转化成只有一个源点和一个汇点的流网络。

求流网络的最大流算法是Ford-Fulkerson算法。首先定义一条边的残留容量是容量减去现有流，由残留容量标示的网络称为残留网络。再定义增广路径是残留网络中从源点s到汇点t的一条路径。Ford-Fulkerson算法是一个迭代过程。每次在残留网络中查找一条增广路径，然后把这条增广路径中最小的一段残留容量加到增广路径各条边的流上，更新残留网络继续迭代，直到找不到增广路径为止。此时退出迭代，现有流就是最大流。

二分图有两部分节点L和R，各部分内部节点之间没有边，即每条边的两个节点都一定分属这两部分，二分图的一个匹配是找到这样一组边，使得每个节点都只有至多一条边与其相连。

二分图的最大匹配问题可以转化为网络最大流问题。增加一个到所有L中顶点容量均为1的源点s和一个所有R中顶点到其容量均为1的汇点t，所有L到R中的边容量也设置为1，现在查找此网络流的最大流就等同于求此二分图的最大匹配。证明过程见算法导论。

POJ2536就是一道二分图最大匹配的应用。题目给出n个老鼠的坐标和m个鼠洞的坐标，如果一只老鼠能在一定时间内到达一个鼠洞，就能躲过老鹰。所以如果某个老鼠与某个鼠洞之间距离小于某值，它俩之间就存在一条边，否则不存在，这是一个明显的二分图。而要求有多少老鼠能躲过老鹰，自然是求此二分图的最大匹配。

代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
 
using namespace std;
 
#define N 205
#define MAX 1000000
 
int capacity[N][N] = {0};
int r_capcity[N][N] = {0};
int fluid[N][N] = {0};
int flag_for_bfs[N][N] = {0};
int s,t;
 
int bfs_findP(vector<int>& p,int numV)
{
	p.clear();
	queue<int> q;
 
	//标记是否已经入过队
	int checked[N] = {0};
 
	q.push(s);
	checked[s] = 1;
 
	int pre[N];
	memset(pre,-1,sizeof(pre)/sizeof(int));
 
	int cur;
 
	//一个节点可以有多个后继，但是只能有一个前驱！因此用一个数组就可以记录找到的路径
	while (!q.empty())
	{
		cur = q.front();
		q.pop();
		if (cur == t)
		{
			break;
		}
 
		for (int i = 0;i < numV;i++)
		{
			if (checked[i] == 0 && cur != i && r_capcity[cur][i] > 0)
			{
				q.push(i);
				checked[i] = 1;
				pre[i] = cur;
 
				/*if (i == t)
				{
					goto outside;
				}*/
			}
		}
	}
 
	if (cur != t)
	{
		return -1;
	}
	int i = pre[cur];
	p.insert(p.begin(),cur);
	while (i != s)
	{
		p.insert(p.begin(),i);
		i = pre[i];
	}
 
	return 0;
}
 
//0.首先设置所有的容量capacity[i][j]
//1.先将所有边的流都置为，
//2.然后迭代：
//更新r_capacity[i][j] = capacity[i][j] - fluid[i][j]
//每次找到一条增广路径，找增广路径使用BFS，增广路径是一条从源点S到汇点T的简单路径
 
//for each edge(u,v) in p 
//	do	f[u,v] <- f[u,v]+fmin
//		f[v,u] <- -f[u,v]
 
 
int max_fluid(int numV)
{
	for (int i = 0;i < numV;i++)
	{
		for (int j = 0;j < numV;j++)
		{
			fluid[i][j] = 0;
			r_capcity[i][j] = capacity[i][j] - fluid[i][j];
		}
	}
	//1 done!
 
	vector<int> p;
	int r_cap = MAX;
	int key_i = -1,key_j = -1;
	while (bfs_findP(p,numV) != -1)
	{
 
 
 
		//find fmin
		r_cap = r_capcity[s][p[0]];
 
		for (int i = 0;i < p.size()-1;i++)
		{
			if (r_capcity[p[i]][p[i+1]] < r_cap)
			{
				r_cap = r_capcity[p[i]][p[i+1]];
				key_i = p[i];
				key_j = p[i+1];
			}
		}
 
		fluid[s][p[0]] += r_cap;
		fluid[p[0]][s] = -fluid[s][p[0]];
 
		for (int i = 0;i < p.size()-1;i++)
		{
			fluid[p[i]][p[i+1]] = fluid[p[i]][p[i+1]] + r_cap;
			fluid[p[i+1]][p[i]] = -fluid[p[i]][p[i+1]];
		}
 
		for (int i = 0;i < numV;i++)
		{
			for (int j = 0;j < numV;j++)
			{
				r_capcity[i][j] = capacity[i][j] - fluid[i][j];
			}
		}
	}
	//2,3,4 done!
 
	int ans = 0;
	for (int i = 0;i < numV;i++)
	{
		if (s != i && fluid[s][i] > 0)
		{
			ans += fluid[s][i];
		}
	}
 
	return ans;
}
 
float distance(float x1,float y1,float x2,float y2)
{
	return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
 
int main()
{
	int n,m,S,V;
	float gophers[105][2],holes[105][2];
 
	while (cin>>n)
	{
		cin>>m>>S>>V;
		for (int i = 0;i < n;i++)
		{
			cin>>gophers[i][0]>>gophers[i][1];
		}
 
		for (int i = 0;i < m;i++)
		{
			cin>>holes[i][0]>>holes[i][1];
		}
 
		for (int i = 0;i < N;i++)
		{
			for (int j = 0;j < N;j++)
			{
				capacity[i][j] = 0;
			}
		}
 
		int numV = m + n + 2;
 
		s = 0;
		t = m + n + 1;
 
		for (int i = 1;i <= n;i++)
		{
			capacity[0][i] = 1;
		}
 
		for (int i = n+1;i <= n+m;i++)
		{
			capacity[i][t] = 1;
		}
 
		for (int i = 1;i <= n;i++)
		{
			for (int j = n+1;j <= n+m;j++)
			{
				if (distance(gophers[i-1][0],gophers[i-1][1],holes[j-n-1][0],holes[j-n-1][1]) <= V*S)
				{
					capacity[i][j] = 1;
				}
			}
		}
 
		cout<<n - max_fluid(numV)<<endl;
	}
}

Leave a Reply