BZOJ (大视野在线测评) Redo Plan 1: 1000 1099

Yuchong Pan edited this page Aug 29, 2018 · 5 revisions

Table of Contents

Solutions

1000: A+B Problem

This is a standard A+B Problem for IO testing purposes.

#include <bits/stdc++.h>

using namespace std;

int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

1001: [BeiJing2006]狼抓兔子

This problem asks for the min-cut of a given lattice-like graph.

The first intuition would be to use the Max-flow min-cut theorem; that is, the min-cut of a network equals its max-flow. Hence, we could use Dinic's algorithm or other max-flow algorithms to compute the min-cut. However, the number of vertices of a given graph can be up to , and the time complexity of Dinic's algorithm is . Hence, we need other algorithms to compute the min-cut.

To solve this problem, we first introduce the idea of Dual graph. According to Wikipedia,

the dual graph of a plane graph is a graph that has a vertex for each face of .

Wikipedia also provides an intuitive picture to illustrate this:

Dual graph

Here, the red graph is the dual graph of the blue graph, and vice versa.

We need to introduce a property of dual graphs:

In a connected planar graph G, every simple cycle of G corresponds to a minimal cutset in the dual of G, and vice versa.

Notice that the problem asks for the min-cut of a given graph. If we convert each face of the given graph to a vertex, then the cycle from the outer face to itself corresponds to a minimal cutset of the original graph, which is asked for. This directly leads to the solution:

We connect the source S and the terminal T to split the outer face into two faces. Then, we convert the original graph to its dual graph, with the newly added edge not in the dual graph (or has infinity weight). After this conversion, we can easily see that the shortest path from one outer face (as we split the original outer face to two) to the other corresponds to the min-cut of the original graph. Hence, we just need to compute the shortest path to get the answer. We can use Dijkstra's algorithm or Shortest Path Faster Algorithm to find the shortest path.

Please note that we need to separately handle cases of n == 1 || m == 1.

#include <bits/stdc++.h>

using namespace std;

const int N0 = 1000 + 5;
const int N = 1000 * 1000 * 2 + 5;
const long long INFTY = 0x7f7f7f7f7f7f7f7fll;

bool v[N];
long long d[N];
int id[N0][N0][2];
vector<pair<int, int> > e[N];

void addedge(int u, int v, int w) {
    e[u].push_back(make_pair(v, w));
    e[v].push_back(make_pair(u, w));
}

long long spfa(int s, int t, int cnt) {
    for (int i = 1; i <= cnt; i++) {
        v[i] = false;
        d[i] = INFTY;
    }
    queue<int> q;
    v[s] = true;
    d[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        v[x] = false;
        for (vector<pair<int, int> >::iterator it = e[x].begin(); it != e[x].end(); it++) {
            int y = it->first, w = it->second;
            if (d[x] + w < d[y]) {
                d[y] = d[x] + w;
                if (!v[y]) {
                    v[y] = true;
                    q.push(y);
                }
            }
        }
    }
    return d[t];
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    if (n == 1 && m == 1) {
        puts("0");
        return 0;
    }
    if (n == 1 || m == 1) {
        int mi = INT_MAX;
        for (int i = 1; i < m + n - 1; i++) {
            int x;
            scanf("%d", &x);
            mi = min(mi, x);
        }
        printf("%d\n", mi);
        return 0;
    }
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            id[i][j][0] = ++cnt;
            id[i][j][1] = ++cnt;
        }
    }
    int s = ++cnt;
    int t = ++cnt;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++) {
            int x;
            scanf("%d", &x);
            if (i == 1) {
                addedge(id[i][j][1], s, x);
            } else if (i == n) {
                addedge(id[i - 1][j][0], t, x);
            } else {
                addedge(id[i - 1][j][0], id[i][j][1], x);
            }
        }
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= m; j++) {
            int x;
            scanf("%d", &x);
            if (j == 1) {
                addedge(id[i][j][0], t, x);
            } else if (j == m) {
                addedge(id[i][j - 1][1], s, x);
            } else {
                addedge(id[i][j - 1][1], id[i][j][0], x);
            }
        }
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            int x;
            scanf("%d", &x);
            addedge(id[i][j][0], id[i][j][1], x);
        }
    }
    printf("%lld\n", spfa(s, t, cnt));
    return 0;
}
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.