Codechef 12.12 DIFTRIP Trie树+后缀自动机+STL
Codechef 14.12 RIN 网络流+最小割

Codechef 12.4 CONNECT 随机化+斯坦纳树

shinbokuow posted @ Dec 02, 2015 08:01:32 PM in Something with tags 随机化 斯坦纳树 , 630 阅读

 

题目大意:
给定一个$n\times{m}$的矩阵,其中每个位置都有一个数,数的范围是$[-1,n\times{m}]$,每个位置还有一个选择这个位置需要付出的代价,每个代价都为正数。
现在要求选择矩阵中的若干个位置组成一个四连通的连通块,使得其中至少有$k$种不同的正数,同时最小化付出的总代价。
数据范围$n,m\leq{15},k\leq{7}$。
算法讨论:
如果数值的范围为$[-1,k]$之间,那么就很好做了,直接利用斯坦纳树模型就可以了。
我们考虑随机将$[1,n\times{m}]$区间中的数映射到$[1,k]$中,然后这样做一次,能得到正确答案的概率为$\frac{k!}{k^k}$,那么我们随机做$T$次,当$T=300$的时候就能够通过Tsinsen上的数据了。
时空复杂度:
时间复杂度$O(T(3^k+2^k\times{SPFA(n\times{m},n\times{m})}))$,空间复杂度$O(nm2^k)$。
代码:
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define inf 0x1f1f1f1f
#define N 16
#define M 16
#define K 7
int n, m, k, a[N][M], w[N][M], ch[N * M];
int f[N][M][1 << K];
queue<pair<int, int> > q;
bool vis[N][M];
static const int dx[] = {-1, 0, 0, 1};
static const int dy[] = {0, -1, 1, 0};
#define inrange(x, l, r) ((x) >= (l) && (x) <= (r))
int main() {
#ifndef ONLINE_JUDGE
    freopen("tt.in", "r", stdin);
#endif
    srand(19980302);
    cin >> n >> m >> k;
    int i, j;
    for (i = 1; i <= n; ++i)
        for (j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]);
    for (i = 1; i <= n; ++i)
        for (j = 1; j <= m; ++j)
            scanf("%d", &w[i][j]);
    
    int T = 300, s, _s, x, y, ans = inf;
    while (T--) {
        for (i = 1; i <= n * m; ++i)
            ch[i] = rand() % k;
        //ch[0] = k;
        memset(f, 0x1f, sizeof f);
        for (i = 1; i <= n; ++i)
            for (j = 1; j <= m; ++j)
                if (a[i][j] == 0)
                    f[i][j][0] = w[i][j];
                else if (a[i][j] != -1)
                    f[i][j][1 << (ch[a[i][j]])] = w[i][j];
        for (s = 1; s < (1 << k); ++s) {
            for (i = 1; i <= n; ++i) {
                for (j = 1; j <= m; ++j) {
                    if (a[i][j] != -1) {
                        for (_s = (s - 1) & s; ; (--_s) &= s) {
                            f[i][j][s] = min(f[i][j][s], f[i][j][_s] + f[i][j][s ^ _s] - w[i][j]);
                            if (_s == 0)
                                break;
                        }
                        if (f[i][j][s] != inf) {
                            vis[i][j] = 1;
                            q.push(make_pair(i, j));
                        }
                    }
                }
            }
            while (!q.empty()) {
                x = q.front().first;
                y = q.front().second;
                q.pop();
                vis[x][y] = 0;
                for (i = 0; i < 4; ++i)
                    if (inrange(x + dx[i], 1, n) && inrange(y + dy[i], 1, m))
                        if (a[x + dx[i]][y + dy[i]] != -1 && f[x + dx[i]][y + dy[i]][s] > f[x][y][s] + w[x + dx[i]][y + dy[i]]) {
                            f[x + dx[i]][y + dy[i]][s] = f[x][y][s] + w[x + dx[i]][y + dy[i]];
                            if (!vis[x + dx[i]][y + dy[i]]) {
                                vis[x + dx[i]][y + dy[i]] = 1;
                                q.push(make_pair(x + dx[i], y + dy[i]));
                            }
                        }
            }
        }
        for (i = 1; i <= n; ++i)
            for (j = 1; j <= m; ++j)
                ans = min(ans, f[i][j][(1 << k) - 1]);
        //printf("%d\n", ans);
    }
    printf("%d\n", ans == inf ? -1 : ans);
    return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter