POJ 1636 Prison rearrangement 二部图连通分量+背包

以第三组为例，我们根据输入可以得到这个二部图

根据不能放在一起的情况可以得到这样的连通分量
对于每一个连通分量，我们将这个连通分量按照监狱分为两个部分
这两个部分调整的时候要作为整体来调整。
**Eg：**我们假设将一号监狱的5调到二号监狱，则二号监狱的5要到一号监狱，随之一号监狱的2,3,4也要调到二号监狱。

所以
①我们找到所有的连通分量，按照监狱各自分为两个部分，视为两个物品
②运用背包模型，对物品进行调整
转态转移

dp[j][k]表示，存在方案使得第一个监狱出j个人，第二个监狱出k个人的调整，j k不一定相等

对于第i个连通分量，第一个监狱对应p1[i]个人，第二个监狱对应p2[i]个人

if( dp[ j-p1[i] ] [ k-p2[i] ] == 1 ){
    dp[j][k] = 1;
}

则有如上关系。
注意由于每一个物品只能使用一次，并且是恰好填满的情况，
所有遍历顺序是从下至上，从右至左。

③遍历dp数组，取得dp[i][i]==1的时候，最大的i值即为答案。
表示一号监狱与二号监狱拿出的人数一样多，切有这样的方案。

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <vector>
#include <cstdio>

using namespace std;

#define debug(x) cout<<#x<<": "<<x<<endl;

int n,m,r;

int p1[201];
int p2[201];
vector<int> danp[401];

bool visit[402];

bool dp[101][101];

int pcnt = 0;
int xi=0;
int yi=0;

void dfs(int a){
    //debug(n)
    visit[a] = 1;
    if( a<=m ){
        p1[pcnt] ++;
    }else{
        p2[pcnt] ++;
    }
    vector<int>&v = danp[a];
    for(int i=0;i < v.size();i++){
        if( visit[ v[i] ] == 0 ){
            dfs(v[i]);
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int nn = 0;nn < n; nn ++){
        scanf("%d%d",&m,&r);

        for(int i=0;i<= m*2;i++){
            danp[i].clear();
        }

        memset(visit,0,sizeof(visit));
        memset(p1,0,sizeof(p1));
        memset(p2,0,sizeof(p2));
        memset(dp,0,sizeof(dp));



        pcnt = 0;
        //debug(000)

        for(int rr=0;rr<r;rr++){

            scanf("%d%d",&xi,&yi);
            danp[xi].push_back(m+yi);
            danp[m+yi].push_back(xi);
        }

        //debug(111)

        for(int i=1;i <= 2*m;i ++){
            if( visit[i] == 0 ){
                dfs(i);
                pcnt++;

            }
        }

        int ret = 0;
        dp[0][0] = 1;
        for(int i = 0;i < pcnt;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] ] == 1 ){
                        dp[j][k] = 1;
                    }
                }
            }
        }
        for(int i = m/2;i >=0;i--){
            if( dp[i][i] == 1 ){
                ret = i;
                break;
            }
        }

        cout<<ret<<endl;
    }
    return 0;
}