题目链接： 

id=1636">POJ 1636 Prison rearrangement

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;

}