[POJ][1636][并查集+背包] Prison rearrangement

描述：

为了降低出现暴动及逃跑事件的风险，两个相同容量的临近监狱的管理层决定重新安排他们的囚犯。他们想用一个监狱里一半的囚犯去交换另一个监狱里一半的囚犯。然而，从囚犯们犯罪史的存档信息可知某些囚犯成对被关在同一座监狱里时会很危险，这也是现今他们被分开的原因，即对于每对这样的囚犯，一名在第一个监狱服刑，另一名在第二座监狱服刑。管理层认同将那些囚犯保持分开的重要性，但这也使得他们的新安排任务有些棘手。事实上，他们很快就了解到有时这个互换一半囚犯的意愿是不可能达成的。每当这种情况下，他们不得不满足于交换尽可能接近一半数量的囚犯。

输入：

输入的第一行是一个正整数n，告诉我们接下来会有多少组测试数据。每组测试数据以一行两个非负整数m和r开头， 1 < m < 200 是两个监狱各自囚犯的数量，r是那些成对的危险囚犯的对数。接下来有r行，每行包含一对范围为[1,m]的整数 xi yi，意思是不能将在第一座监狱服刑的xi与在第二座监狱服刑的yi安排至同一座监狱。

输出：

对于每组测试数据，输出一行包含一个整数 k <= m/2 ，这是在没把成对的危险囚犯关在同一座监狱的前提下，两个监狱所能交换囚犯的最大数量。

思路：

并查集加背包。首先利用并查集将两个监狱之间有危险关系的囚犯放置在同一个集合中，例如第一个监狱的1号囚犯和2号囚犯与第二个监狱的3号囚犯处于同一所监狱时会很危险，那么便将这三人放置在一个集合中。

经过上述步骤，我们已经有了多个集合。若想将集合中的任意一个人安排到另一个监狱，那么集合中的其他人也得被迫移动。明确了这一点，问题便可以被简化为，移动哪些集合里的人可以使两个监狱交换的人数相等且尽可能接近m/2。

这个简化后的问题很明显可以用动归思想来解决，例如背包。将每个集合中第一个监狱的人数抽象为费用，第二个监狱的人数抽象为价值，集合数量抽象为物品数量，总钱数为m/2。如此一来原始问题就再次被简化为在花费res且购得物品的总价值刚好也为res的情况下，求解res的最大值。

代码：

#include
#include
#include
using namespace std;
int m,r,f[401],mark[401],n,c[401],w[401];
//m个囚犯、r对危险囚犯 
//f[]用于并查集，记录每个节点的父节点
//mark[]用于trans()，判断一个父节点是否访已被问过。
//接下来是用于背包的数组 
//n件物品，第i件物品的费用是c[i]、价值是w[i]。
bool dp[101][101]; 
//dp[i][j]表示费用刚好为i的时候，是否存在价值为j的解。 
int max(int a,int b)
{
    return a>b?a:b;
}
void init()
//初始化 
{
    for(int i=1;i<=400;i++)
    {
        mark[i]=c[i]=w[i]=0;
        f[i]=i;
    }
    for(int i=0;i<=100;i++)
        for(int j=0;j<=100;j++)
            dp[i][j]=false;
    dp[0][0]=true;
    n=1;
}
int find(int x)
//用于并查集，寻找x的父节点。 
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}
void union_set(int x,int y)
//用于并查集，将x所在的集合与y所在的集合合并。 
{
    int px=find(x);
    int py=find(y);
    if(px!=py)
        f[px]=py;
}
void input()
//输入 
{
    scanf("%d%d",&m,&r);
    for(int i=0;i=c[i];j--)
        //从m/2到c[i]遍历费用 
            for(int k=m/2;k>=w[i];k--)
            //从m/2到w[i]遍历价值 
                if(dp[j-c[i]][k-w[i]])
                //若存在费用为j-c[i]且价值为k-w[i]的方案 
                {
                    dp[j][k]=true;
                    //那么费用为j其价值为k的方案也一定存在。 
                    if(j==k)
                    //价值与价值相同，即交换人数相同。 
                        res=res>k?res:k;
                        //res记录最大值，即结果。 
                }
    printf("%d\n",res);
}
int main()
{
    int t;
    for(scanf("%d",&t);t>0;t--)
    {
        init();
        input();
        trans();
        solve();
    }
}