「Solution」最大权闭合子图 习题

Posted on Edited on In

做题记录

小M的作物

$\mathcal{Link}$

link

$\mathcal{Sol}$

直接用文理分科思路直接碾过去

如果非要用最大权闭合子图解释也是可以的。
那么可以先把每个点分别向 $A,B$ 集合连边， 可以清晰地看到其中的依赖关系， 即是每个额外价值依赖于其中的作物。

然后建虚点表示额外价值向每个作物连边即可。

$\mathcal{Code}$

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
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e6 + 5;
const int MAXM = 1e7 + 5;
const int INF = 0x3f3f3f3f;

int n, m, cnt, cur[MAXM], d[MAXM], deg[MAXN];
int st, ed, ans, tmp, tot = 1, head[MAXM], nxt[MAXM], edge[MAXM], ver[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) {
    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;
}

signed main() {
    
    // freopen("1.in", "r", stdin);
    // freopen("D.out", "w", stdout);

    scanf("%d", &n);
    st = n + 1, ed = cnt = n + 2;

    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        AddEdge(st, i, x);
        ans += x;
    }   

    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        AddEdge(i, ed, x);
        ans += x;
    }

    scanf("%d", &m);
    for (int i = 1, k, c1, c2; i <= m; i++) {
        scanf("%d %d %d", &k, &c1, &c2);
        cnt++; 
        AddEdge(st, cnt, c1);
        AddEdge(cnt + 1, ed, c2);
        ans += c1, ans += c2;
        for (int j = 1, v; j <= k; j++) {
            scanf("%d", &v);
            AddEdge(cnt, v, INF);
            AddEdge(v, cnt + 1, INF);
        }
        cnt++;
    }

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

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

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

	return 0;
}

Strange Set

$\mathcal{Link}$

link

$\mathcal{Sol}$

体验 $5 \ minutes' \ time$ 快速切掉 2700 的 F 的快感。

显然的依赖关系，即是 $a_i$ 依赖于 $a_j \mid a_i (1 \le j < i)$。
没看空限，直接 $\mathbb{MLE \ on \ test \ 14}$

寻求思辨。
发现对于每个因数，只需要连最后的那个就行了。

$\mathcal{Code}$

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
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 6e5 + 5;
const int MAXM = 6e5 + 5;
const int INF = 0x3f3f3f3f;

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

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) {
	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;
}

signed main() {

	scanf("%d", &n);
	st = n + 1, ed = n + 2;

	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) scanf("%d", &b[i]);

	for (int i = 1; i <= n; i++) {
		if (b[i] > 0) AddEdge(st, i, b[i]), ans += b[i];
		else AddEdge(i, ed, -b[i]);
	}

	for (int i = 1; i <= n; i++) {
		memset(vis, 0, sizeof(vis));
		for (int j = i - 1; j >= 1; j--) {
			if (a[i] % a[j] == 0 && vis[a[j]] == 0) {
				AddEdge(i, j, INF);
				vis[a[j]] = 1;
			}
		}
	}

	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.」