过山车

题目链接：hdu - 2063

题意：求二分图的最大匹配

思路：二分图最大匹配模板题，利用匈牙利算法解决，其核心是通过不停地找增广路来增加匹配中的匹配边和匹配点，找不到增广路时，达到最大匹配

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1010;

struct node {
    int to, nex;
};

node edge[N * N];
int k, n, m, used[N], nex[N];
int cnt, head[N];

void add_edge(int u, int v)
{
    edge[++cnt].to = v;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

bool find(int u)
{
    for (int i = head[u]; 0 != i; i = edge[i].nex) {
        int v = edge[i].to;
        if (!used[v]) {
            used[v] = 1;
            if (nex[v] == 0 || find(nex[v])) {
                nex[v] = u;
                return true;
            }
        }
    }
    return false;
}

int match()
{
    int res = 0;
    for (int i = 1; i <= n; i++) {
        memset(used, 0, sizeof(used));
        if (find(i)) res++;
    }
    return res;
}

int main()
{
    while (scanf("%d", &k) && k) {
        cnt = 0;
        memset(head, 0, sizeof(head));
        memset(nex, 0, sizeof(nex));
        scanf("%d%d", &n, &m);
        while (k--) {
            int u, v;
            scanf("%d%d", &u, &v);
            add_edge(u, n + v);
        }
        printf("%d\n", match());
    }
    return 0;
}

Antenna Placement

题目链接：poj - 3020

题意：在平面上有若干点，可以用一个圆圈覆盖相邻的两个点，问最少需要多少圆圈能将所有点覆盖

思路：二分图求最小路径覆盖，关键在于如何建图，可以采用黑白相间染色的办法，被染成黑色的点放在一个集合，被染成白色的点放在另一个集合，将相邻的黑色点和白色点之间连一条边，求出最大匹配数，二分图最小路径覆盖数=点的总数-二分图最大匹配数

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 50;
const int M = 410;

struct node {
    int nex, to;
};

int T, h, w, n, m, b[N][N];
int used[M], nex[M], head[M], cnt;
node edge[M * M];
char s[N][N];

void add_edge(int u, int v)
{
    edge[++cnt].to = v;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

bool find(int u)
{
    for (int i = head[u]; 0 != i; i = edge[i].nex) {
        int v = edge[i].to;
        if (used[v]) continue;
        used[v] = 1;
        if (0 == nex[v] || find(nex[v])) {
            nex[v] = u;
            return true;
        }
    }
    return false;
}

int match()
{
    int res = 0;
    for (int i = 1; i <= n; i++) {
        memset(used, 0, sizeof(used));
        if (find(i)) res++;
    }
    return res;
}

void init()
{
    cnt = 0;
    memset(nex, 0, sizeof(nex));
    memset(head, 0, sizeof(head));
    memset(b, 0, sizeof(b));
}

int main()
{
    scanf("%d", &T);
    while (T--) {
        init();
        scanf("%d%d", &h, &w);
        for (int i = 1; i <= h; i++) scanf("%s", s[i] + 1);
        n = m = 0;
        for (int i = 1; i <= h; i++) {
            for (int k = 1; k <= w; k++) {
                if ('*' != s[i][k]) continue;
                if (0 == (i + k) % 2) b[i][k] = ++n;
                else b[i][k] = ++m;
            }
        }
        for (int i = 1; i <= h; i++) {
            for (int k = 1; k <= w; k++) {
                if ('*' != s[i][k] || 0 != (i + k) % 2) continue;
                if (b[i - 1][k]) add_edge(b[i][k], n + b[i - 1][k]);
                if (b[i + 1][k]) add_edge(b[i][k], n + b[i + 1][k]);
                if (b[i][k + 1]) add_edge(b[i][k], n + b[i][k + 1]);
                if (b[i][k - 1]) add_edge(b[i][k], n + b[i][k - 1]);
            }
        }
        int res = match();
        printf("%d\n", n + m - res);
    }
    return 0;
}

Treasure Exploration

题目链接：poj - 2594

题意：给出一个由n个点m条边组成的有向无环图，求最少需要多少路径，使得这些路径可以覆盖所有点，每个点可以被多条路径覆盖

思路：二分图求最小路径覆盖，因为有的点可以被多条路径覆盖，可能存在相交路径，所以先要用floyd求出传递闭包，将求最小可相交路径转换成最小不可相交路径，然后再用二分图求最小路径覆盖，最小路径覆盖数=点的总数-二分图最大匹配数

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 510;

int n, m, f[N][N];
int used[N], nex[N];

void floyd()
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                f[i][j] |= (f[i][k] & f[k][j]);
}

bool find(int u)
{
    for (int i = 1; i <= n; i++) {
        if (!used[i] && f[u][i]) {
            used[i] = 1;
            if (0 == nex[i] || find(nex[i])) {
                nex[i] = u;
                return true;
            }
        }
    }
    return false;
}

int match()
{
    int res = 0;
    for (int i = 1; i <= n; i++) {
        memset(used, 0, sizeof(used));
        if (find(i)) res++;
    }
    return res;
}

int main()
{
    while (scanf("%d%d", &n, &m) && 0 != (n + m)) {
        memset(nex, 0, sizeof(nex));
        memset(f, 0, sizeof(f));
        while (m--) {
            int u, v;
            scanf("%d%d", &u, &v);
            f[u][v] = 1;
        }
        floyd();
        int res = match();
        printf("%d\n", n - res);
    }
    return 0;
}