学步园

http://www.cnblogs.com/zhaoguanqin/archive/2012/04/03/2430895.html

题目大意：有两个牢房，人数相等，都为m，现在要求交换这两个牢房的囚犯，其中有些囚犯是不能放在同一个牢房的，要你求出交换次数最大为多少，且不超过m/2

解题思路：动态规划+深度优先遍历。

dp[i][i]表示i对人交换成功。

标记出两个牢房A,B, A中的元素ai到B中的元素bj,

因为动一个牢房的人，由于连带关系，会牵涉到很多人。

所以分别从左边牢房的第一个人开始考虑，直到最后一个人，看左右两边交换的人数为多少

然后再从右边牢房的第一个人开始考虑，直到最后一个人，看左右两边交换的人数为多少。

假设l, r分别表示左右两个牢房的交换人数

dp[i][j] = dp[i - l][j - r]

下面程序中的graph[x][y] = true表示左右牢笼囚犯编号x,y不能放在一起

之前写成了graph[x][y] = graph[y][x] = true, wa了好几次

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 210;

int t, m, n;
bool graph[maxn][maxn], visited[2][maxn], dp[maxn][maxn];

void dfs(int flag, int index, int &l, int &r);

int main()
{
	scanf("%d", &t);
	while(t-- != 0)
	{
		memset(graph, 0, sizeof(graph));
		memset(dp, 0, sizeof(dp));
		memset(visited, 0, sizeof(visited));
		scanf("%d %d", &m, &n);
		int x, y;
		for(int i = 0; i < n; i++)
		{
			scanf("%d %d", &x, &y);
			graph[x][y] = true; //之前写的是graph[x][y] = graph[y][x] = true, wa了好几次，这是因为分别从左右两个牢笼选取人考虑，所以不用建立双向边 
		}
		dp[0][0] = true;
		for(int k = 1; k <= m; k++)
		{
			if(visited[0][k])
				continue;
			int l = 0, r = 0;
			dfs(0, k, l, r);
			for(int i = m / 2; i >= l; i--)
			{
				for(int j = m / 2; j >= r; j--)
				{
					if(dp[i - l][j - r])
						dp[i][j] = true; //因为是从第一个人开始递增选取的，所以确定i,j时，1~i-1, 1~j-1已经确定好了。 
				}
			}
		}
		for(int k = 1; k <= m; k++)
		{
			if(visited[1][k])
				continue;
			int l = 0, r = 0;
			dfs(1, k, l, r);
			for(int i = m / 2; i >= l; i--)
			{
				for(int j = m / 2; j >= r; j--)
				{
					if(dp[i - l][j - r])
						dp[i][j] = true;
				}
			}
		}
		
		for(int i = m / 2; i >= 0; i--)
		{
			if(dp[i][i])
			{
				printf("%d\n", i);
				break;
			}
		}
	}
	
	return 0;
}

void dfs(int flag, int index, int &l, int &r)
{
	visited[flag][index] = true;
	if(flag == 1)
	{
		r++;
		for(int i = 1; i <= m; i++)
		{
			if(!visited[0][i] && graph[i][index])
				dfs(0, i, l, r);
		}
	}
	else
	{
		l++;
		for(int i = 1; i <= m; i++)
		{
			if(!visited[1][i] && graph[index][i])
				dfs(1, i, l, r);
		}
	}
}

第二种方法传递闭包 + dp的思想，只是在处理连通性不一样。

把右边囚犯的编号编码成与左边的囚犯的编码不一样，然后通过floyd算法求出这个图的连通性，最后从第一个点开始枚举选取每个点要牵涉的左右两个牢笼中的人数，并保存起来用于后面的dp用

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 210;

int t, m, n, left[maxn], right[maxn];
bool graph[2 * maxn][2 * maxn], visited[2 * maxn], dp[maxn][maxn];

int main()
{
	
	scanf("%d", &t);
	while(t-- != 0)
	{
		memset(graph, 0, sizeof(graph));
		memset(dp, 0, sizeof(dp));
		memset(visited, 0, sizeof(visited));
		memset(left, 0, sizeof(left)); 
		memset(right, 0, sizeof(right)); 
		scanf("%d %d", &m, &n);
		for(int i = 0; i <= 2 * m; i++) 
			graph[i][i] = true; 
		int x, y;
		for(int i = 0; i < n; i++)
		{
			scanf("%d %d", &x, &y);
			graph[x][y + m] = graph[y + m][x] = true; 
		}
		
		for(int k = 1; k <= 2 * m; k++)
		{
			for(int i = 1; i <= 2 * m; i++)
			{
				if(graph[i][k])
				{
					for(int j = 1; j <= 2 * m; j++)
					{
						graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]); 
						
					}
				} 
			} 
		}
		
		int cnt = 0;
		for(int i = 1; i <= 2 * m; i++) 
		{
			if(!visited[i])
			{
				cnt++;
				for(int j = 1; j <= 2 * m; j++)
				{
					if(graph[i][j])
					{
						if(j <= m)
							left[cnt]++;
						else
							right[cnt]++; 
						visited[j] = true; 
					} 
				} 
			} 
		}
		
		dp[0][0] = true; 
		for(int k = 1; k <= cnt; k++)
		{
			for(int i = m / 2; i >= left[k]; i--)
			{
				for(int j = m / 2; j >= right[k]; j--)
				{
					if(dp[i - left[k]][j - right[k]])
						dp[i][j] = true;
				} 
			} 
		} 
		
		for(int i = m / 2; i >= 0; i--)
		{
			if(dp[i][i])
			{
				printf("%d\n", i);
				break;
			}
		}
	}
	
	return 0;
}