首页 > 代码库 > POJ 1636 Prison rearrangement DFS+0/1背包
POJ 1636 Prison rearrangement DFS+0/1背包
题目链接: POJ 1636 Prison rearrangement
Time Limit: 3000MS | Memory Limit: 10000K | |
Total Submissions: 2194 | Accepted: 984 |
Description
Input
Output
Sample Input
3 101 0 3 3 1 2 1 3 1 1 8 12 1 1 1 2 1 3 1 4 2 5 3 5 4 5 5 5 6 6 7 6 8 7 8 8
Sample Output
50 0 3
Source
题意:
有两个监狱都有m个囚犯,现在为了更好地管理,需要相互交换一部分人(小于等于m/2)。但是有一个问题就是,某一些有冲突的人的人不能待在一个监狱里面。也就是说,监狱1中的囚犯A和监狱2的囚犯B如果放在一起的话,将会产生很严重的后果。现在你要求出可行的最大交换人数(不大于一半),使得有冲突的人不能待在一个监狱里面。
思路:
这道题卡了挺久,网上看了很多题解,然后自己认真想了想,发觉自己对背包的理解还不是很透彻。
想想看,首先要将有关系的人分开成一个个集合(p, q),表示监狱1中要拿出p个人交换的话,监狱2得同时拿出q个人。如何找到这个集合呢?细心地人一眼就看出了是求连通分量了。
先构图,因为两个监狱的囚犯的人数和编号都是一样的,为了构图方便,我们将第二个监狱的囚犯的便后向后挪m(+m)。然后有关系的两个人之间连一条无向边。之后的事情就交给dfs求连通分支了,当然中间要记录监狱1和监狱2需要交换多少个人。
那现在我们得到了cnt个连通分支了,也就是有cnt个集合(p, q),现在看看0/1背包的思想。我们用二维数组来记录在不发生危险的情况下可进行交换的情况,dp[i][j] = true表示第一个监狱拿出i个人、第二个监狱拿出j个人进行交换不产生冲突的情况。利用滚动数组的思想,从后往前更新所有可能情况。因为最后要保证两个监狱交换人数相同,因而找到最大的i使dp[i][i] == true,i(《= m/2)就是我们要求的结果。
代码:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int m, g[402][402]; int p1[202], p2[202], dp[110][110]; int cnt; bool vis[402]; void dfs(int s) { vis[s] = true; if(s <= m) p1[cnt]++; else p2[cnt]++; for(int i = 1; i <= 2*m; i++) if(!vis[i] && g[s][i]) dfs(i); } int main() { int t, r, a, b; //freopen("out.txt", "w", stdout); scanf("%d", &t); while(t--) { scanf("%d%d", &m, &r); memset(g, 0, sizeof(g)); while(r--) { scanf("%d%d", &a, &b); g[a][b+m] = g[b+m][a] = 1; } memset(vis, false, sizeof(vis)); cnt = 0; for(int i = 1; i <= 2*m; i++) if(!vis[i]) { p1[cnt]= p2[cnt] = 0; dfs(i); cnt++; } memset(dp, false, sizeof(dp)); dp[0][0] = true; for(int i = 0; i < cnt; i++) for(int j = m/2; j >= p1[i]; j--) for(int k = m/2; k >= p2[i]; k--) if(dp[j-p1[i]][k-p2[i]]) dp[j][k] = true; int index = m/2; for(int i = m/2; i >= 0; i--) if(dp[i][i]) { index = i; break; } printf("%d\n", index); } return 0; }