dango

[POJ 1636] Prison rearrangement

原题地址： http://acm.pku.edu.cn/JudgeOnline/problem?id=1636

题目大意：

拥有同样容量m的两个监狱打算交换一些犯人（<=m/2），但是有一些囚犯不可以放在同一个监狱里头。问最多可以交换多少人（再多也不能超过m/2）

题目分析：

不妨把监狱称为A和B。当存在牵连关系时，A中的某个犯人移动到B，会牵动B中一些犯人移动到A，如此反复……其实也就是如果要移动A，其最终结果是A中的一部分人和B中的一部分人整体交换。那么就需要求出这样的一个交换关系（传递闭包)。

思路：

用一个暴力的Floyd来解决传递闭包的问题，再用一个经典的二维背包来解决移动问题。其实算法都是很基础的，但是还是TLE了两次，原因在于对一些细节的不注意。

有些时候看似危险的复杂度，其实只要把一些细节考虑好了，就可以从TLE跨越到AC。尤其是常见的floyd，加了一行小小的连优化都不算的判断就从TLE变为AC了。

下面代码里头把原来TLE的部分也留在注释里，自己引以为戒。

代码：

POJ 1636
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int maxn = 410;

int m, group, Afree, Bfree;
bool map[maxn][maxn];
int A_size[maxn], B_size[maxn];

void init(){
    int i, r;
    scanf("%d%d", &m, &r);
    memset(map, 0, sizeof(bool)*maxn*maxn);
    for (i=1; i<=2*m; i++)
        map[i][i] = 1;
    for (i=1; i<=r; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        b += m;                            //B监狱中的点编号自加m，方便floyd 
        map[a][b] = map[b][a] = 1;
    }
}

void floyd(){
    int i,j,k;
    for (j=1; j<=2*m; j++)
        for (i=1; i<=2*m; i++)
            if (map[i][j])                //  添加完这个，从TLE --> AC  important!!!!!
            for (k=1; k<=2*m; k++)
                map[i][k] = map[i][k] || (map[i][j] && map[j][k]);
}

void build(){
    int i,j,k;
    int color[maxn];
    group = 0;
    memset(color, 0, sizeof(int)*maxn);
    memset(A_size,  0, sizeof(int)*maxn);
    memset(B_size,  0, sizeof(int)*maxn);
    Afree = Bfree = 0;
    for (i=1; i<=2*m; i++)                    //枚举所有点 
        if (color[i] == 0){                    //如果未染色 
            ++group;
            for (j=1; j<=2*m; j++)
                if (map[i][j]){                //如果属于一个大组（原来在一监狱需要一起移动，不在一个监狱则会冲突 
                    color[j] = group;
                    if (j<=m)  A_size[group]++;
                    else B_size[group]++;
                }
            if (A_size[group] == 1 && B_size[group] == 0){
                color[i] = 0;
                Afree++;
                A_size[group--] = 0;
            }
            else
            if (B_size[group] == 1 && A_size[group] == 0){
                color[i] = 0;
                Bfree++;
                B_size[group--] = 0;
            }
        }
}

void solve(){
    int i,j,k;
    bool f[maxn][maxn];                        //f[i][j] == true 表示A移动i人B移动j人是可以的 
    memset(f, 0, sizeof(bool)*maxn*maxn);
    for (i=0; i<=Afree; i++)
        for (j=0; j<=Bfree; j++)
            f[i][j] = 1;
//    for (i=0; i<=m; i++)
//        for (j=0; j<=m; j++)
//            for (k=1; k<=group; k++)        //枚举交换的组
//                if (i-A_size[k]>=0 && j-B_size[k]>=0 && f[i-A_size[k]][j-B_size[k]])
//                    f[i][j] = 1;
// 更换循环次序，也可以带来时间上的大大节省！ 
    for (k=1; k<=group; k++)
        for (i=m/2 - A_size[k]; i>=0; i--)
            for (j=m/2 - B_size[k]; j>=0; j--)
                if (f[i][j] && i+A_size[k]<=m/2 && j+B_size[k]<=m/2)
                    f[i+A_size[k]][j+B_size[k]] = 1;
    for (i=m/2; i>=0; i--)
        if (f[i][i]) break;
    printf("%d\n", i);
}

int main(){
    int T;
    scanf("%d", &T);
    while (T--){
        init();
        floyd();
        build();
        solve();
    }
    system("pause");
    return 0;
}