「Solution」文理分科 & 圈地计划

Posted on Edited on In

网络流建图

文理分科

link

分析

可以知道，每个点只能选择 文/理 中的一种，那么可以将其转化为一个二分图最小割的问题。

把每个点的贡献拆开，一部分是自己选科后的贡献 art_i或science_i ，一部分是与相邻同学在一起产生的贡献 same_art_i 或 same_science_i。

那么把点分成 i ， i' ， i''。

如下图

pic

将i'向周围的四个点j1~j4连边，边权为same_art_i，再将j1~j4向i''

连边，边权为same_science_i。

为什么是对的呢？

因为根据最小割定义，它会将图分成两个集合。

由于题目中二选一的限制，划分后可以保证每个学生只选一门。

代码

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 5e2 + 5;
const int MAXM = 5e7 + 5;
const int INF = 0x3f3f3f3f;
const int dx[5] = {0, 1, -1, 0, 0};
const int dy[5] = {0, 0, 0, 1, -1};

int n, m, st, ed, now, ans, tmp, d[MAXM], cur[MAXM];
int art[MAXN][MAXN], sci[MAXN][MAXN], sa[MAXN][MAXN], ss[MAXN][MAXN];
int tot = 1, head[MAXM], ver[MAXM], edge[MAXM], nxt[MAXM];
queue<int> q;

void AddEdge(int u, int v, int c) {
 	// printf("%d %d %d\n", u, v, c);
    ver[++tot] = v, edge[tot] = c, nxt[tot] = head[u], head[u] = tot;
    ver[++tot] = u, edge[tot] = 0, nxt[tot] = head[v], head[v] = tot;
}

bool bfs() {
    memset(d, 0, sizeof(d));
    while (!q.empty()) q.pop();
    q.push(st), d[st] = 1, cur[st] = head[st];

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = nxt[i]) {
            int v = ver[i];
            if (!edge[i] || d[v] != 0) continue;
            q.push(v); cur[v] = head[v];
            d[v] = d[u] + 1;
            if (v == ed) return true;
        }
    }

    return false;

}

int dinic(int u, int flow) {
//  printf("%d %d %d\n", now, u, d[u]);
    if (u == ed) return flow;
    int res = flow, k, i;
    for (i = cur[u]; i && res; i = nxt[i]) {
        int v = ver[i];
        if (!edge[i] || d[v] != d[u] + 1) continue;
        now++;
        k = dinic(v, min(res, edge[i]));
        now--;
        if (k == 0) d[v] = 0;
        edge[i] -= k, edge[i ^ 1] += k;
        res -= k;
        cur[u] = i;
    }
    return flow - res;
}

int ind(int x, int y) { return (x - 1) * m + y; }
int ind1(int x, int y) { return (x - 1) * m + y + n * m; }
int ind2(int x, int y) { return (x - 1) * m + y + n * m * 2; }


int main() {

	// freopen("B.out", "w", stdout);

	scanf("%d %d", &n, &m);

	st = n * m * 3 + 1, ed = n * m * 3 + 2;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) scanf("%d", &art[i][j]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) scanf("%d", &sci[i][j]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) scanf("%d", &sa[i][j]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) scanf("%d", &ss[i][j]);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			AddEdge(st, ind(i, j), art[i][j]);
			AddEdge(ind(i, j), ed, sci[i][j]);
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			AddEdge(st, ind1(i, j), sa[i][j]);
			AddEdge(ind2(i, j), ed, ss[i][j]);
			for (int k = 0; k <= 4; k++) {
				int nx = i + dx[k], ny = j + dy[k];
				// printf("%d %d\n", nx, ny);
				if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
				AddEdge(ind1(i, j), ind(nx, ny), INF);
				AddEdge(ind(nx, ny), ind2(i, j), INF);
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ans += art[i][j] + sci[i][j] + sa[i][j] + ss[i][j];
		}
	}

    while (bfs()) {
        while ((tmp = dinic(st, INF))) {
            ans -= tmp;
        }
    }

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

    return 0;
}

圈地计划

link

分析

其实可以转换到与上一道题差不多。
但是它对周围造成的贡献是反的。

考虑黑白染色。
如果当前点是黑的，那么就把 a_i 和 b_i 交换，即可完成反向。

代码

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e3 + 5;
const int MAXM = 5 * 1e6 + 5;
const int dx[5] = {0, 0, 0, 1, -1};
const int dy[5] = {0, 1, -1, 0, 0};
const int INF = 0x3f3f3f3f;

int n, m, a[MAXN][MAXN], b[MAXN][MAXN], c[MAXN][MAXN], cur[MAXM], d[MAXM];
int st, ed, ans, tmp, tot = 1, head[MAXM], nxt[MAXM], edge[MAXM], ver[MAXM];

int ind(int x, int y) {
	return (x - 1) * m + y;
}

queue<int> q;

void AddEdge(int u, int v, int c) {
    ver[++tot] = v, edge[tot] = c, nxt[tot] = head[u], head[u] = tot;
    ver[++tot] = u, edge[tot] = 0, nxt[tot] = head[v], head[v] = tot;
}

bool bfs() {
    memset(d, 0, sizeof(d));
    while (!q.empty()) q.pop();
    q.push(st), d[st] = 1, cur[st] = head[st];

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = nxt[i]) {
            int v = ver[i];
            if (!edge[i] || d[v] != 0) continue;
            q.push(v); cur[v] = head[v];
            d[v] = d[u] + 1;
            if (v == ed) return true;
        }
    }

    return false;

}

int dinic(int u, int flow) {
    if (u == ed) return flow;
    int res = flow, k, i;
    for (i = cur[u]; i && res; i = nxt[i]) {
        int v = ver[i];
        if (!edge[i] || d[v] != d[u] + 1) continue;
        k = dinic(v, min(res, edge[i]));
        if (k == 0) d[v] = 0;
        edge[i] -= k, edge[i ^ 1] += k;
        res -= k;
        cur[u] = i;
    }
    return flow - res;
}

int main() {

	scanf("%d %d", &n, &m);

	st = n * m * 4 + 1, ed = n * m * 4 + 2;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
			ans += a[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &b[i][j]);
			ans += b[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &c[i][j]);
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {

			if ((i & 1) == (j & 1)) {
				swap(a[i][j], b[i][j]);
			}

			AddEdge(st, ind(i, j), a[i][j]);
			AddEdge(ind(i, j), ed, b[i][j]);

			for (int k = 1; k <= 4; k++) {
				int nx = i + dx[k];
				int ny = j + dy[k];
				if (nx < 1 || ny < 1 || nx > n || ny > m) continue;

				AddEdge(ind(i, j), ind(nx, ny), c[i][j] + c[nx][ny]);

				ans += c[i][j];

			}
		}
	}

	while (bfs()) {
		while ((tmp = dinic(st, INF))) ans -= tmp;
	}

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

	return 0;
}
The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」