Chaos Slover 补档计划 - 斯坦纳树

2015.12.08 22:16 Tue| 2 visits oi_2016| ChaosSlover补档计划| Text

关于常数的优化

关于数组寻址

1
2
3
4
int sum = 0;
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
        ans += f[i][j];
1
2
3
4
int sum = 0;
for (int i = 1; i <= m; ++i)
    for (int j = 1; j <= n; ++j)
        ans += f[j][i];

这两段代码有区别么?有!而且区别还很大!区别有多大?二到四倍常数!

本来一个数组好好地开在一块连续的内存里,从前往后一个一个找当然会比较快。下面的那一段代码相当于在内存里面东一块西一块地查找,不慢才怪 = =。

关于 vector 和 deque

1
2
3
deque<int> q;
for (int i = n; i >= 0; --i) q.push_back(i);
sort(q.begin(), q.end());
1
2
3
vector<int> v;
for (int i = n; i >= 0; --i) v.push_back(i);
sort(v.begin(), v.end());

vector 和 deque 的功能差不多,只是 deque 多了一个 pop_front() 功能而已。然而在实现上,vector 使用的总是一块连续内存,均摊时间复杂度 O(1),但寻址会快于 deque。deque 大概是类似于双向链表的结构,内存不连续,寻址较慢,但对于头和尾的操作还是很快的。

于是在进行排序的时候 vector 会快于 deque(其实并不快多少的说,只能优化一丁点小常数)。

BZOJ2595 [Wc2008]游览计划

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f

const int dx[] = {0, 1, -1, 0, 0}, dy[] = {0, 0, 0, 1, -1};

int n, m, k, c[15][15], b[15][15];
int f[2500][15][15], vis[15][15];
queue<pair<int, int> > q;

struct data
{
    int x, y, z;
    data() {}
    data(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}
} pre[15][15][2500];

void spfa(int s)
{
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (f[s][i][j] != inf)
                q.push(make_pair(i, j)), vis[i][j] = true;
    while (!q.empty())
    {
        int x = q.front().first, y = q.front().second; q.pop();
        vis[x][y] = false;
        for (int i = 1; i <= 4; ++i)
        {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 1 || tx > n || ty < 1 || ty > m) continue;
            if (f[s][tx][ty] > f[s][x][y] + c[tx][ty])
            {
                f[s][tx][ty] = f[s][x][y] + c[tx][ty],
                pre[tx][ty][s] = data(x, y, s);
                if (!vis[tx][ty])
                    q.push(make_pair(tx, ty)), vis[tx][ty] = true;
            }
        }
    }
}

void getans(int x, int y, int s)
{
    if (pre[x][y][s].z == 0) return;
    vis[x][y] = 1;
    getans(pre[x][y][s].x, pre[x][y][s].y, pre[x][y][s].z);
    getans(pre[x][y][s].x, pre[x][y][s].y, s - pre[x][y][s].z);
}

int main()
{
    memset(f, 0x3f, sizeof f);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            cin >> c[i][j];
            if (c[i][j] == 0) f[1 << (k++)][i][j] = 0;
        }
    int s = 1 << k;
    for (int i = 1; i < s; ++i)
    {
        for (int j = 1; j < i; ++j)
            if (j == (i & j))
                for (int x = 1; x <= n; ++x)
                    for (int y = 1; y <= m; ++y)
                        if (f[i][x][y] > f[j][x][y] + f[i ^ j][x][y] - c[x][y])
                            f[i][x][y] = f[j][x][y] + f[i ^ j][x][y] - c[x][y],
                            pre[x][y][i] = data(x, y, j);
        spfa(i);
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (c[i][j] == 0)
            {
                cout << f[s - 1][i][j] << endl;
                getans(i, j, s - 1); goto end;
            }
    end: ;
    for (int i = 1; i <= n; ++i, puts(""))
        for (int j = 1; j <= m; ++j)
            putchar(c[i][j] ? (vis[i][j] ? 'o' : '_') : 'x');
    return 0;
}

BZOJ4006 [JLOI2015]管道连接

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f

int n, m, p, f[1050][1050], g[1050];
int head[1050], vis[1050];
pair<int, int> d[15];

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[6005];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

queue<int> q;

void spfa(int s)
{
    for (int i = 1; i <= n; ++i)
        if (f[s][i] != inf)
            q.push(i), vis[i] = true;
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        vis[x] = false;
        for (int i = head[x]; i; i = edge[i].next)
            if (f[s][edge[i].to] > f[s][x] + edge[i].val)
            {
                f[s][edge[i].to] = f[s][x] + edge[i].val;
                if (!vis[edge[i].to])
                    q.push(edge[i].to), vis[edge[i].to] = true;
            }
    }
}

void steiner_tree(int n, int k)
{
    int s = 1 << k;
    for (int i = 1; i < s; ++i)
    {
        for (int j = 1; j < i; ++j)
            if (j == (i & j))
                for (int x = 1; x <= n; ++x)
                    f[i][x] = min(f[i][x], f[j][x] + f[i ^ j][x]);
        spfa(i);
    }
}

int main()
{
    cin >> n >> m >> p;
    for (int x, y, z, i = 1; i <= m; ++i)
        x = read(), y = read(), z = read(),
        add(x, y, z), add(y, x, z);
    for (int x, y, i = 1; i <= p; ++i)
        x = read(), y = read(), d[i] = make_pair(x, y);
    sort(d + 1, d + p + 1);
    int s = 0;
    for (int i = 1; i <= p; ++i)
        d[i].first = d[i].first == d[i + 1].first ? s : s++;
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= p; ++i)
        f[1 << (i - 1)][d[i].second] = 0;
    steiner_tree(n, p);
    s = 1 << s;
    for (int i = 1; i < s; ++i)
    {
        int pos = 0;
        for (int j = 1; j <= p; ++j)
            if (i & (1 << d[j].first))
                pos += (1 << (j - 1));
        for (int j = 1; j <= p; ++j)
            if (i & (1 << d[j].first))
                { g[i] = f[pos][d[j].second]; break; }
    }
    for (int i = 1; i < s; ++i)
        for (int j = 1; j < i; ++j)
            if (j == (i & j))
                g[i] = min(g[i], g[j] + g[i ^ j]);
    cout << g[s - 1] << endl;
    return 0;
}

BZOJ3205&UOJ107【APIO2013】ROBOTS

用记忆化搜索预处理出从每个点出发向四周移动一次将会到达的最终位置,相当于从这个点和四个位置之间连有权值为 1 的单向边。之后运用类似于斯坦纳树的方法求解。由于序号相邻的限制,这道题的时间复杂度不再是指数级的了,仅为 O(N^3 * HW + N^2 * SPFA(HW, 4*HW))!

哇!这两道题的代码长度都是刚好 100 行耶!

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>
using namespace std;

#define N 505
#define inf 0x3f3f3f3f

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};

int n, w, h, f[10][10][N][N];
char s[N][N];
pair<int, int> pos[10], to[N][N][4];

struct data
{
    int x, y, z;
    data() {}
    data(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}
    bool operator <(const data &d) const { return z < d.z; }
    void get(int &_x, int &_y, int &_z) { _x = x, _y = y, _z = z; }
};

void dfs(int x, int y, int d)
{
    static bool v[N][N][4];
    if (v[x][y][d]) return; v[x][y][d] = true;
    int tx = x + dx[d], ty = y + dy[d];
    if (s[tx][ty] == 'x')
    {
        to[x][y][d] = make_pair(x, y);
    }
    else
    {
        int td = (d + (s[tx][ty] == 'A' ? 3 : (s[tx][ty] == 'C' ? 1 : 0))) % 4;
        dfs(tx, ty, td), to[x][y][d] = to[tx][ty][td];
    }
}

void bfs(int l, int r)
{
    deque<data> q1, q2;
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            if (f[l][r][i][j] != inf)
                q2.push_back(data(i, j, f[l][r][i][j]));
    sort(q2.begin(), q2.end());
    while (!q1.empty() || !q2.empty())
    {
        int x, y, z;
        if (q1.empty() || (!q2.empty() && q2.front() < q1.front()))
            q2.front().get(x, y, z), q2.pop_front();
        else q1.front().get(x, y, z), q1.pop_front();
        pair<int, int> *t = to[x][y];
        for (int i = 0; i < 4; ++i)
        {
            if (!t[i].first) continue;
            if (f[l][r][t[i].first][t[i].second] > f[l][r][x][y] + 1)
                f[l][r][t[i].first][t[i].second] = f[l][r][x][y] + 1,
                q1.push_back(data(t[i].first, t[i].second, f[l][r][x][y] + 1));
        }
    }
}

int steiner_tree()
{
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= n; ++i)
        f[i][i][pos[i].first][pos[i].second] = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 1; j + i <= n; bfs(j, j + i), ++j)
            for (int m = 0; m < i; ++m)
                for (int x = 1; x <= h; ++x)
                    for (int y = 1; y <= w; ++y)
                        f[j][j + i][x][y] = min(f[j][j + i][x][y],
                            f[j][j + m][x][y] + f[j + m + 1][j + i][x][y]);
    int re = inf;
    for (int x = 1; x <= h; ++x)
        for (int y = 1; y <= w; ++y)
            re = min(re, f[1][n][x][y]);
    return re == inf ? -1 : re;
}

int main()
{
    cin >> n >> w >> h;
    memset(s, 'x', sizeof s);
    for (int i = 1; getchar(), i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            s[i][j] = getchar();
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            if (s[i][j] != 'x')
            {
                for (int d = 0; d < 4; ++d)
                    dfs(i, j, d);
                if (isdigit(s[i][j]))
                    pos[s[i][j] - '0'] = make_pair(i, j);
            }
    cout << steiner_tree() << endl;
    return 0;
}