2010-1115

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目意思就是要在方格纸中建围墙，使X和E无法联通，然后X每能和一个A联通收入就会增加这个A对应的权值，画圈的花费是所经过的边权之和（经过两次就算两次）。
做法：
1、枚举圈上的一点作为起点，状态dist[i][j][k]表示从这个起点出发到达i,j点，且经过各A点向右的射线为奇数次的mask为k（有点拗口，等等详细解释）时的最小画圈花费，那么，回到起点的dist[i][j][k]值就表示画圈包含在内的点的mask为k时的最小花费。
2、这样就可以得到单独的一个圈包含的点为mask时所需要的最小花费A[mask]，但是最终建好的围墙不一定只是一个圈，有可能是好几个圈，还需要对mask再行枚举得到结果。

对1中k的意义的解释：
  当我们定好起点后，设想每个点都向右射出一条射线，那么，当我们从起点画圈再返回起点时，如果穿过了某条射线奇数次的话，说明我们把对应的这个点包在了圈中（射线法判点在多边形内），于是，我们在这个圈尚未画好，还是一条路径的时候，就可以记录它穿越某条射线的次数的奇偶次，把这些状态压缩成mask，就得到了k

{{{
#!cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#define MP make_pair
using namespace std;

const int MAXN = 31;
const int INF = 0x3f3f3f3f;

int N, M, K;
int di[4] = {0, 0, -1, 1};
int dj[4] = {-1, 1, 0, 0};
int bi[4] = {0, 0, -1, 1};
int bj[4] = {-1, 0, 0, 0};
int cost[MAXN * 2][MAXN], mat[MAXN * 2][MAXN];
int dist[MAXN][MAXN][1 << 6];
bool in[MAXN][MAXN][1 << 6];
int add[10], num[10];

inline bool ok(int i, int j){   
    return (0 <= i && i <= N && 0 <= j && j <= M);      
}
inline void border(int i, int j, int dir, int & ret1, int & ret2){
    switch(dir){
        case 0:
        case 1:
            i = i * 2;
            j -= (1 - dir);
            break;
        case 2: 
        case 3:
            i = (i + dir - 2) * 2 - 1;
            break;
    }
    ret1 = mat[i][j];
    ret2 = cost[i][j];  
}
int tot;
void bfs(int i, int j){
        int k, pi, pj, nk, co, dir;
    memset(dist, 0x3f, sizeof(dist));
    memset(in, 0, sizeof(in));
    dist[i][j][0] = 0;
    priority_queue <pair <int, int> > Q;
    Q.push(MP(0, ((i << 4) | j) << 6));
        while (!Q.empty()){
        ++tot;
        i = (Q.top().second >> 10);
        j = ((Q.top().second >> 6) & 15);
        k = (Q.top().second & 63);
        int tmp = dist[i][j][k];
        if (tmp != -Q.top().first){
            Q.pop();
            continue;
        }   
        Q.pop();
        for (dir = 0; dir < 4; ++dir){
            pi = i + di[dir];
            pj = j + dj[dir];
            if (ok(pi, pj)){
                nk = k ^ mat[i * 2 + bi[dir]][j + bj[dir]];
                co = cost[i * 2 + bi[dir]][j + bj[dir]];
                if (dist[pi][pj][nk] > tmp + co){
                    dist[pi][pj][nk] = tmp + co;
                    Q.push(MP(-dist[pi][pj][nk], (((pi << 4) | pj) << 6) | nk));                    
                }
            }
        }
    }
}

int main(){
    int i, j, k, x;
    int mask;
    int A[1 << 6], out[1 << 6];
    while (scanf("%d%d", &N, &M) != EOF){
        tot = 0;
        for (i = 0; i < 2 * N + 1; ++i){
            for (j = 0; j < M + (i & 1); ++j){
                scanf("%d", &cost[i][j]);
            }
        }       
        memset(mat, 0, sizeof(mat));
        scanf("%d", &K);
        for (mask = k = 0; k < K; ++k){
            scanf("%d%d%d", &add[k], &i, &j);           
            if (add[k] == 0)
                x = k;
            for (i = i * 2 + 1, ++j; j <= M; ++j)
                mat[i][j] |= (1 << k);
        }
        memset(A, 0x3f, sizeof(A));
        for (i = 0; i < N; ++i){
            for (j = 0; j < M; ++j){
                bfs(i, j);              
                for (k = 0; k < (1 << K); ++k){
                    A[k] = min(A[k], dist[i][j][k]);
                }   
            }
        }
        memset(out, 0x3f, sizeof(out));
        for (k = 0; k < (1 << K); ++k){
            out[k] = A[k];
        }
        for (k = 0; k < (1 << K); ++k){
            for (i = k; i > 0; i = (i - 1) & k)
                out[k] = min(out[k], A[i] + out[k ^ i]);
        }
        int ans = INF, now;
        for (k = 0; k < (1 << K); ++k){
            if (k & (1 << x)){
                for (mask = now = i = 0; i < K; ++i)
                    if ((k & (1 << i))){
                        if (add[i] >= 0){
                            now -= add[i];
                        } else {
                            mask |= (1 << i);
                        }
                    }
                ans = min(ans, now + out[mask] + A[k]);
            }
        }

        printf("%d\n", ans);
    }
}
}}}

题目意思就是要在方格纸中建围墙，使X和E无法联通，然后X每能和一个A联通收入就会增加这个A对应的权值，画圈的花费是所经过的边权之和（经过两次就算两次）。

做法：

1、枚举圈上的一点作为起点，状态dist[i][j][k]表示从这个起点出发到达i,j点，且经过各A点向右的射线为奇数次的mask为k（有点拗口，等等详细解释）时的最小画圈花费，那么，回到起点的dist[i][j][k]值就表示画圈包含在内的点的mask为k时的最小花费。

2、这样就可以得到单独的一个圈包含的点为mask时所需要的最小花费A[mask]，但是最终建好的围墙不一定只是一个圈，有可能是好几个圈，还需要对mask再行枚举得到结果。

对1中k的意义的解释：

当我们定好起点后，设想每个点都向右射出一条射线，那么，当我们从起点画圈再返回起点时，如果穿过了某条射线奇数次的话，说明我们把对应的这个点包在了圈中（射线法判点在多边形内），于是，我们在这个圈尚未画好，还是一条路径的时候，就可以记录它穿越某条射线的次数的奇偶次，把这些状态压缩成mask，就得到了k

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#define MP make_pair
using namespace std;
const int MAXN = 31;
const int INF = 0x3f3f3f3f;
int N, M, K;
int di[4] = {0, 0, -1, 1};
int dj[4] = {-1, 1, 0, 0};
int bi[4] = {0, 0, -1, 1};
int bj[4] = {-1, 0, 0, 0};
int cost[MAXN * 2][MAXN], mat[MAXN * 2][MAXN];
int dist[MAXN][MAXN][1 << 6];
bool in[MAXN][MAXN][1 << 6];
int add[10], num[10];
inline bool ok(int i, int j){   
    return (0 <= i && i <= N && 0 <= j && j <= M);      
}
inline void border(int i, int j, int dir, int & ret1, int & ret2){
    switch(dir){
        case 0:
        case 1:
            i = i * 2;
            j -= (1 - dir);
            break;
        case 2: 
        case 3:
            i = (i + dir - 2) * 2 - 1;
            break;
    }
    ret1 = mat[i][j];
    ret2 = cost[i][j];  
}
int tot;
void bfs(int i, int j){
        int k, pi, pj, nk, co, dir;
    memset(dist, 0x3f, sizeof(dist));
    memset(in, 0, sizeof(in));
    dist[i][j][0] = 0;
    priority_queue <pair <int, int> > Q;
    Q.push(MP(0, ((i << 4) | j) << 6));
        while (!Q.empty()){
        ++tot;
        i = (Q.top().second >> 10);
        j = ((Q.top().second >> 6) & 15);
        k = (Q.top().second & 63);
        int tmp = dist[i][j][k];
        if (tmp != -Q.top().first){
            Q.pop();
            continue;
        }   
        Q.pop();
        for (dir = 0; dir < 4; ++dir){
            pi = i + di[dir];
            pj = j + dj[dir];
            if (ok(pi, pj)){
                nk = k ^ mat[i * 2 + bi[dir]][j + bj[dir]];
                co = cost[i * 2 + bi[dir]][j + bj[dir]];
                if (dist[pi][pj][nk] > tmp + co){
                    dist[pi][pj][nk] = tmp + co;
                    Q.push(MP(-dist[pi][pj][nk], (((pi << 4) | pj) << 6) | nk));                    
                }
            }
        }
    }
}
int main(){
    int i, j, k, x;
    int mask;
    int A[1 << 6], out[1 << 6];
    while (scanf("%d%d", &N, &M) != EOF){
        tot = 0;
        for (i = 0; i < 2 * N + 1; ++i){
            for (j = 0; j < M + (i & 1); ++j){
                scanf("%d", &cost[i][j]);
            }
        }       
        memset(mat, 0, sizeof(mat));
        scanf("%d", &K);
        for (mask = k = 0; k < K; ++k){
            scanf("%d%d%d", &add[k], &i, &j);           
            if (add[k] == 0)
                x = k;
            for (i = i * 2 + 1, ++j; j <= M; ++j)
                mat[i][j] |= (1 << k);
        }
        memset(A, 0x3f, sizeof(A));
        for (i = 0; i < N; ++i){
            for (j = 0; j < M; ++j){
                bfs(i, j);              
                for (k = 0; k < (1 << K); ++k){
                    A[k] = min(A[k], dist[i][j][k]);
                }   
            }
        }
        memset(out, 0x3f, sizeof(out));
        for (k = 0; k < (1 << K); ++k){
            out[k] = A[k];
        }
        for (k = 0; k < (1 << K); ++k){
            for (i = k; i > 0; i = (i - 1) & k)
                out[k] = min(out[k], A[i] + out[k ^ i]);
        }
        int ans = INF, now;
        for (k = 0; k < (1 << K); ++k){
            if (k & (1 << x)){
                for (mask = now = i = 0; i < K; ++i)
                    if ((k & (1 << i))){
                        if (add[i] >= 0){
                            now -= add[i];
                        } else {
                            mask |= (1 << i);
                        }
                    }
                ans = min(ans, now + out[mask] + A[k]);
            }
        }
        printf("%d\n", ans);
    }
}