算法-图论-专题练习

发表于 更新于

目前共计 19 道题。

通信线路-二分+双端队列最短路

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
# include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, M = 20 * N;

int head[N], ne[M], edge[M], weight[M], tot = 1;

int n, m, k;

int dist[N];
bool st[N]; 

void add(int x, int y, int w)
{
    edge[++tot] = y, weight[tot] = w;
    ne[tot] = head[x], head[x] = tot; 
}

int check(int mid) 
{
    // check mid 检查大于mid的最短路上边的数量的值，
    // 如果小于等于k，则mid是一个可选项，说明选择mid后，
    // 只有不大于k条边大于 mid
    // 我们希望这个值恰好等于k
    // 所以若返回值小于等于k，则继续减小mid
    deque<int> dq;
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof(st));
    dq.push_back(1);
    dist[1] = 0;

    while (dq.size())
    {
        int x = dq.front();
        dq.pop_front();
        if (st[x])
            continue;
        st[x] = true;
        for (int i = head[x]; ~i; i = ne[i])
        {
            int y = edge[i], w = weight[i] > mid;
            if (dist[y] > dist[x] + w)
            {
                dist[y] = dist[x] + w;
                if (w == 1)
                    dq.push_back(y);
                else
                    dq.push_front(y);
            }
        }
    }
    return dist[n];
}

int main()
{
    memset(head, -1, sizeof(head));
    cin >> n >> m >> k;
    int l = 0, r = 1e6 + 1;
    while (m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid) <= k)
            r = mid;
        else
            l = mid + 1;
    }
    if (r != 1e6 + 1)
        cout << r;
    else
        cout << -1;
}

排序-二分+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
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
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 27, M = N * N;

int n, m;
PII relation[M];
bool grid[N][N];

void rebuild_grid(int p)
{
    memset(grid, 0, sizeof(grid));
    for (int i = 1; i <= p; ++i)
    {
        int a, b;
        tie(a, b) = relation[i];
        grid[a][b] = true;
    }
}

int check(int p)    // 考虑前k个指令时的结果
{
    rebuild_grid(p);
    int type = 0; // 0 is success, 1 is failure, 2 is not sure
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                grid[i][j] |= grid[i][k] & grid[k][j];
    
    for (int i = 1; i <= n; ++i)
        if (grid[i][i])
            return 1;

    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (!grid[i][j] && !grid[j][i])
            {
                type = 2;
                break;
            }
    return type;
}

string top_sort(int p)
{
    rebuild_grid(p);
    int in[N] = {0};
    for (int i = 1; i <= n; ++i)        //calculate in degree of vertex i (i = ch - 'A' + 1)
        for (int j = 1; j <= n; ++j)
            if (grid[i][j])
                ++in[j];
    
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (in[i] == 0)
            q.push(i);

    
    string res = "";
    while (q.size())
    {
        int u = q.front();
        q.pop();
        res += char(u + 'A' - 1);
        for (int i = 1; i <= n; ++i)
            if (in[i] > 0 && grid[u][i])
            {
                --in[i];
                if (in[i] == 0)
                    q.push(i);
            }
    }
    return res;
}

int main()
{
    while (cin >> n >> m)
    {
        if (n == 0 && m == 0)
            break;
        for (int i = 1; i <= m; ++i)
        {
            char a, b, tmp;
            cin >> a >> tmp >> b;
            relation[i] = {a - 'A' + 1, b - 'A' + 1};
        }
        int type = check(m);
        int l = 0, r = m;
        while (l < r)
        {
            int mid = l + r >> 1;
            int mid_type = check(mid);
            if (mid_type == 0)
                r = mid, type = 0;
            else if (mid_type == type)
                r = mid;
            else
                l = mid + 1;
        }
        if (type == 0)
            printf("Sorted sequence determined after %d relations: %s.\n", r, top_sort(r).c_str());
        else if (type == 1)
            printf("Inconsistency found after %d relations.\n", r);
        else
            printf("Sorted sequence cannot be determined.\n");
    }
}

走廊泼水节-Kruskal

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
#include <bits/stdc++.h>
using namespace std;
const int N = 6e3 + 10, M = N * 2;

struct Edge{ int x, y, z; } edges[M];

int n;
int p[N];
int cnt[N];

int find(int x)
{
    if (p[x] == x)
        return x;
    return p[x] = find(p[x]);
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i < n; ++i)
            cin >> edges[i].x >> edges[i].y >> edges[i].z;
        sort(edges + 1, edges + n, [](Edge a, Edge b) -> bool
            { return a.z < b.z; });

        long long res = 0;
        for (int i = 1; i <= n; ++i)
            p[i] = i, cnt[i] = 1;
        
        for (int i = 1; i < n; ++i)
        {
            int a = find(edges[i].x);
            int b = find(edges[i].y);
            int w = edges[i].z;
            res += (w + 1) * (cnt[a] * cnt[b] - 1);
            p[a] = b;
            cnt[b] += cnt[a];
        }
        cout << res << endl;
    }
}

Railway System-Kruskal

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
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int M = 510;

int n, m;
PII l[M]; // first 表示长度， second 表示排序前的序号
int s[M]; // 排序完毕后的那个什么

void query(string s) { cout << "? " << s << endl; }

int main()
{
    cin >> n >> m;

    string q = string(m, '0');
    for (int i = 0; i < m; ++i)
    {
        q[i] = '1';
        query(q);
        q[i] = '0';
        cin >> l[i].first;
        l[i].second = i;
    }
    sort(l, l + m);
    for (int i = 0; i < m; ++i)
    {
        int index = l[i].second;
        q[index] = '1';
        query(q);
        cin >> s[i + 1];
    }
    int res = 0;
    for (int i = 0; i < m; ++i)
        if (s[i + 1] == s[i] + l[i].first)
            res += l[i].first;
    cout <<"! " << res << endl;
}

巡逻-树的直径

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 <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;

int head[N], ne[M], edge[M], weight[M], tot = 1;
int dist[N]; // 表示以 x 为子树根节点时，走向子树的叶节点的最长路径（认为 1 是整棵树的根）
// dp方程： D[x] = max(D[x], D[y] + e(x, y)), 其中 y 是 x 的子节点
int n, K;
int res2 = 0;
int b_dist[N]; // 使用bfs时的dist，表示最远距离
int fa[N];     // 记录的是前往父节点的反向边

void add(int a, int b)
{
    edge[++tot] = b, weight[tot] = 1;
    ne[tot] = head[a], head[a] = tot;
}

void dp(int x, int p = -1)
{
    // get diameter
    for (int i = head[x]; ~i; i = ne[i])
    {
        int y = edge[i];
        if (y == p)
            continue;
        dp(y, x);
        res2 = max(res2, dist[x] + dist[y] + weight[i]);
        dist[x] = max(dist[x], dist[y] + weight[i]);
    }
}

void dfs(int u, int p = -1)
{
    // get diameter, and set all edges in diameter -1
    for (int i = head[u]; ~i; i = ne[i])
    {
        int v = edge[i];
        if (v == p)
            continue;
        if (b_dist[v] > b_dist[u] + 1)
        {
            b_dist[v] = b_dist[u] + 1;
            fa[v] = i ^ 1;
            dfs(v, u);
        }
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    cin >> n >> K;
    for (int i = 1; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    if (K == 1)
        dp(1), cout << 2 * n - res2 - 1 << endl;
    else
    {
        memset(b_dist, 0x3f, sizeof(b_dist));
        b_dist[1] = 0;
        dfs(1);
        int p = 1, q = 1;
        for (int i = 1; i <= n; ++i)
            if (b_dist[i] > b_dist[p])
                p = i;
        memset(b_dist, 0x3f, sizeof(b_dist));
        b_dist[p] = 0;
        dfs(p);
        for (int i = 1; i <= n; ++i)
            if (b_dist[i] > b_dist[q])
                q = i;
        int res1 = 0;
        while (p != q)
        {
            int v = edge[fa[q]];
            weight[fa[q]] = weight[fa[q] ^ 1] = -1;
            res1 += 1;
            q = v;
        }
        dp(1);
        cout << 2 * n - res1 - res2 << endl;
    }
}

How far away?-LCA

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 <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 4e4 + 10, K = 20;

int n, m;
int head[N], edge[2 * N], weight[2 * N], ne[2 * N], tot = 0;
int depth[N];
int f[N][K];

void add(int a, int b, int c)
{
    edge[++tot] = b, weight[tot] = c;
    ne[tot] = head[a], head[a] = tot;
}

void build()
{
    memset(depth, 0, sizeof(depth));
    queue<int> q;
    depth[1] = 1;
    q.push(1);

    while (q.size())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = ne[i])
        {
            int v = edge[i];
            if (depth[v])
                continue;
            depth[v] = depth[u] + 1;
            f[v][0] = u;
            for (int j = 1; j < 20; j++)
                f[v][j] = f[f[v][j - 1]][j - 1];
            q.push(v);
        }
    }
}

int lca(int x, int y) // caculate path from x to y
{
    if (depth[x] > depth[y])
        swap(x, y); // make sure depth[x] <= depth[y]

    for (int i = 19; i >= 0; --i)
        if (depth[f[y][i]] >= depth[x])
            y = f[y][i];
    if (x == y)
        return x;
    for (int i = 19; i >= 0; --i)
        if (f[x][i] != 0 && f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}

int length(int x, int y, int p) // caculate path from x to y through dfs
{
    if (x == y)
        return 0;
    for (int i = head[x]; ~i; i = ne[i])
    {
        int v = edge[i], w = weight[i];
        if (p == v)
            continue;
        if (v == y)
            return w;
        int recur = length(v, y, x);
        if (recur != 0)
            return recur + w;
    }
    return 0;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        memset(head, -1, sizeof(head));
        cin >> n >> m;
        for (int i = 1; i < n; ++i)
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
            add(b, a, c);
        }
        build();
        while (m--)
        {
            int x, y;
            cin >> x >> y;
            int z = lca(x, y);
            cout << length(x, z, -1) + length(y, z, -1) << endl;
        }
    }
}

学校网络-强连通分量

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
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
const int N = 110, M = N * N;

int n;
int head[N], edge[M], ne[M], tot = 0;
stack<int> stk;
bool ins[N];                          // in stack
int dfn[N], low[N], num = 0, cnt = 0; // num shows dfn_code, cnt shows scc_cnt
vector<int> scc[N];
int c[N]; // shows scc identifier of i
int hc[N], ec[N], nc[M], tc = 0;
int in_c[N], out_c[N];

void add(int a, int b)
{
    edge[++tot] = b;
    ne[tot] = head[a], head[a] = tot;
}

void tarjan(int x)
{
    dfn[x] = low[x] = ++num;
    stk.push(x), ins[x] = true;
    for (int i = head[x]; ~i; i = ne[i])
    {
        int y = edge[i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (ins[y])
            low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        cnt++;
        int y;
        do
        {
            y = stk.top(), ins[y] = 0;
            stk.pop();
            c[y] = cnt, scc[cnt].push_back(y);
        } while (x != y);
    }
}

void add_c(int x, int y)
{
    ec[++tc] = y;
    nc[tc] = hc[x], hc[x] = tc;
}

int main()
{
    memset(head, -1, sizeof(head));
    memset(hc, -1, sizeof(hc));
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int j;
        while (cin >> j, j)
            add(i, j);
    }
    for (int i = 1; i <= n; ++i)
        if (!dfn[i])
            tarjan(i);
    for (int x = 1; x <= n; ++x)
    {
        for (int i = head[x]; ~i; i = ne[i])
        {
            int y = edge[i];
            if (c[x] == c[y])
                continue;
            add_c(c[x], c[y]);
            in_c[c[y]]++, out_c[c[x]]++;
        }
    }
    int p = 0, q = 0;
    for (int i = 1; i <= cnt; ++i)
    {
        if (!in_c[i])
            p++;
        if (!out_c[i])
            q++;
    }
    cout << p << endl;
    if (cnt == 1)
        cout << 0 << endl;
    else
        cout << max(p, q) << endl;
}

Sightseeing Cows-spfa判断负环

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 5010;

int n, m;
int head[N], ne[M], edge[M], weight[M], tot = 0;
int fun[N];
double dist[N];
int cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    edge[++tot] = b, weight[tot] = c;
    ne[tot] = head[a], head[a] = tot;
}

bool check(double mid) // 检测有无负环，有负环则最大值一定大于mid，置 l = mid
{

    for (int i = 1; i <= n; ++i)
        dist[i] = 0x3f3f3f3f3f;
    memset(cnt, 0, sizeof(dist));
    memset(st, 0, sizeof(st));
    queue<int> q;
    q.push(1);
    st[1] = true;
    dist[1] = 0;

    while (q.size())
    {
        int u = q.front();
        q.pop();
        st[u] = false;
        for (int i = head[u]; ~i; i = ne[i])
        {
            int v = edge[i];
            double w = mid * weight[i] - fun[u];
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n)
                    return true;
                if (!st[v])
                    st[v] = true, q.push(v);
            }
        }
    }
    return false;
}

int main()
{
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> fun[i];
    for (int i = 1; i <= m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    double l = 0, r = 1000;
    while (r - l > 1e-6)
    {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    printf("%.2lf\n", l);
}

棋盘覆盖-匈牙利算法

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
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 110;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int n, t, ans = 0;
PII match[N][N];
bool vis[N][N];
bool inv[N][N];

bool dfs(int x, int y)
{
    for (int i = 0; i < 4; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 1 || a > n || b < 1 || b > n || inv[a][b])
            continue;
        if (!vis[a][b])
        {
            vis[a][b] = true;
            if (match[a][b] == make_pair(0, 0) || dfs(match[a][b].first, match[a][b].second))
            {
                match[a][b] = make_pair(x, y);
                return true;
            }
        }
    }
    return false;
}

int main()
{
    cin >> n >> t;
    for (int i = 1; i <= t; i++)
    {
        int x, y;
        cin >> x >> y;
        inv[x][y] = true;
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if ((i + j) & 1)
            {
                memset(vis, 0, sizeof(vis));
                if (!inv[i][j] && dfs(i, j))
                    ans++;
            }
    cout << ans << endl;
}

Sum of Distances in Tree-换根DP

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
func sumOfDistancesInTree(n int, edges [][]int) []int {
	adjs := make([][]int, n)
	for i := range adjs {
		adjs[i] = make([]int, 0)
	}
	for i := range edges {
		adjs[edges[i][0]] = append(adjs[edges[i][0]], edges[i][1])
		adjs[edges[i][1]] = append(adjs[edges[i][1]], edges[i][0])
	}
	dp, sz := make([]int, n), make([]int, n)
	var dfs func(u, p int)
	dfs = func(u, p int) {
		sz[u]++
		for _, v := range adjs[u] {
			if v == p {
				continue
			}
			dfs(v, u)
			dp[u] += dp[v] + sz[v]
			sz[u] += sz[v]
		}
	}
	dfs(0, -1)
	var change func(u, p int)
	ans := make([]int, n)
	change = func(u, p int) {
		// root is u, and switch to v
		ans[u] = dp[u]
		for _, v := range adjs[u] {
			if p == v {
				continue
			}
			dp[u] -= dp[v] + sz[v]
			sz[u] -= sz[v]
			sz[v] += sz[u]
			dp[v] += dp[u] + sz[u]
			change(v, u)
			dp[v] -= dp[u] + sz[u]
			sz[v] -= sz[u]
			sz[u] += sz[v]
			dp[u] += dp[v] + sz[v]
		}
	}
	change(0, -1)
	return ans
}

关押罪犯-染色法+二分

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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10, M = 2e5 + 10;

int n, m;
int head[N], edge[M], ne[M], weight[M], tot = 0;
int color[N];

void add(int a, int b, int c)
{
    edge[++tot] = b, weight[tot] = c;
    ne[tot] = head[a], head[a] = tot;
}

bool dfs(int u, int c, int mid)
{
    color[u] = c;
    bool flag = true;
    for (int i = head[u]; ~i; i = ne[i])
    {
        int v = edge[i], w = weight[i];
        if (w <= mid)
            continue;
        if (!color[v])
            flag &= dfs(v, 3 ^ c, mid);
        else if (color[v] == color[u])
            return false;
    }
    return flag;
}

bool check(int mid)
{ // 忽略所有小于等于mid的边，是否为二分图
    memset(color, 0, sizeof(color));
    bool flag = true;
    for (int i = 1; i <= n; i++)
        if (!color[i])
            flag &= dfs(i, 1, mid);
    return flag;
}

int main()
{
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    int l = 0, r = 1e9 + 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << endl;
}

机器任务-二分图最小点覆盖

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
#include <bits/stdc++.h>
using namespace std;
const int N = 210, M = 2e3 + 10;

// n ~ n + m - 1 为 B 的模式
int n, m, k;
int head[N], ne[M], edge[M], tot = 0;
bool vis[N];
int match[N];

void add(int a, int b)
{
    edge[++tot] = b;
    ne[tot] = head[a], head[a] = tot;
}

bool dfs(int x)
{
    for (int i = head[x]; ~i; i = ne[i])
    {
        int y = edge[i];
        if (!vis[y])
        {
            vis[y] = true;
            if (match[y] == -1 || dfs(match[y]))
            {
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    while (cin >> n, n)
    {
        cin >> m >> k;
        memset(head, -1, sizeof(head));
        memset(match, -1, sizeof(match));
        tot = 0;
        for (int i = 1; i <= k; i++)
        {
            int a, b, c;
            cin >> a >> b >> c;
            if (b == 0 || c == 0)
                continue;
            add(b, c + n);
            add(c + n, b);
        }
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            memset(vis, 0, sizeof(vis));
            if (dfs(i))
                res++;
        }
        cout << res << endl;
    }
}

泥泞的区域-二分图最小点覆盖

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
#include <bits/stdc++.h>
using namespace std;
const int N = 55, M = N * N;

int n, m;
char grid[N][N];
int h[N][N], v[N][N]; // 横、竖放的板子对应的编号

int p = 1, q = 1; // 横、竖的块数
int head[M], edge[M * 2], ne[M * 2], tot = 0;
bool vis[M];
int match[M];

void add(int a, int b)
{
    edge[++tot] = b;
    ne[tot] = head[a], head[a] = tot;
}

bool dfs(int x)
{
    for (int i = head[x]; ~i; i = ne[i])
    {
        int y = edge[i];
        if (!vis[y])
        {
            vis[y] = true;
            if (!match[y] || dfs(match[y]))
            {
                match[y] = x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> grid[i][j];
    for (int i = 1; i <= n; i++)
    {
        int cnt = 0;
        for (int j = 1; j <= m; j++)
        {
            if (grid[i][j] == '*')
            {
                cnt++, h[i][j] = p;
                if (j == m)
                    p++;
            }
            else if (cnt)
            {
                cnt = 0;
                p++;
            }
        }
    }
    for (int j = 1; j <= m; j++)
    {
        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            if (grid[i][j] == '*')
            {
                cnt++, v[i][j] = q;
                if (i == n)
                    q++;
            }
            else if (cnt)
            {
                cnt = 0;
                q++;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (grid[i][j] == '*')
                add(h[i][j], v[i][j]);
    int ans = 0;
    for (int i = 1; i <= p; i++)
    {
        memset(vis, 0, sizeof(vis));
        if (dfs(i))
            ans++;
    }
    cout << ans;
}

骑士放置-二分图最大独立集

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
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 110;

int n, m, t;
int grid[N][N]; // 1 2 表示染色，3 表示禁止放置
int dx[] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
PII match[N][N];
bool vis[N][N];

bool limit(int i, int j)
{
    return i < 1 || i > n || j < 1 || j > m || grid[i][j] == 3;
}

void color(int x, int y, int c)
{
    grid[x][y] = c;
    for (int i = 0; i < 8; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (limit(a, b))
            continue;
        if (!grid[a][b])
            color(a, b, 3 ^ c);
    }
}

bool dfs(int x, int y)
{
    for (int i = 0; i < 8; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if (limit(a, b))
            continue;
        if (!vis[a][b])
        {
            vis[a][b] = true;
            if (match[a][b].first == 0 || dfs(match[a][b].first, match[a][b].second))
            {
                match[a][b] = make_pair(x, y);
                return true;
            }
        }
    }
    return false;
}

int main()
{
    cin >> n >> m >> t;
    for (int i = 1; i <= t; i++)
    {
        int a, b;
        cin >> a >> b;
        grid[a][b] = 3;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (!grid[i][j])
                color(i, j, 1);
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            memset(vis, 0, sizeof(vis));
            if (grid[i][j] == 1 && dfs(i, j))
                cnt++;
        }
    cout << n * m - t - cnt;
}

奖金-判环+拓补排序

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, M = 2e4 + 10;

int n, m;
int head[N], edge[M], ne[M], tot = 0;
int ind[N];
int vis[N];
int dp[N];

void add(int a, int b)
{
    edge[++tot] = b;
    ne[tot] = head[a], head[a] = tot;
}

bool dfs(int u)
{
    vis[u] = 1;
    for (int i = head[u]; ~i; i = ne[i])
    {
        int v = edge[i];
        if (vis[v] == -1)
            continue;
        if (vis[v] == 1)
            return true;
        if (dfs(v))
            return true;
    }
    vis[u] = -1;
    return false;
}

bool hasLoop()
{
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++)
        if (vis[i] == 0 && dfs(i))
            return true;
    return false;
}

int main()
{
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        add(b, a);
        ind[a]++;
    }
    if (hasLoop())
        cout << "Poor Xed" << endl;
    else
    {
        queue<int> q;
        memset(vis, 0, sizeof(vis));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++)
            if (ind[i] == 0)
                q.push(i), dp[i] = 100;
        while (q.size())
        {
            int u = q.front();
            q.pop();
            vis[u] = 1;
            for (int i = head[u]; ~i; i = ne[i])
            {
                int v = edge[i];
                if (vis[v])
                    continue;
                ind[v]--;
                dp[v] = max(dp[v], dp[u] + 1);
                if (ind[v] == 0)
                    q.push(v);
            }
        }
        long long sum = 0;
        for (int i = 1; i <= n; i++)
            sum += dp[i];
        cout << sum << endl;
    }
}

昂贵的聘礼

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
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 110, M = N * N;
// 由于 n 较小，所以假设酋长地位位 q
// 依次检测只和 q-m~q，直到 q~q+m 的最小值
// 100*5500 log(100)

int m, n;
int head[N], ne[M], edge[M], weight[M], tot = 0;
int price[N], level[N];

void add(int a, int b, int c)
{
    edge[++tot] = b, weight[tot] = c;
    ne[tot] = head[a], head[a] = tot;
}

bool st[N];
int dist[N];
int dij(int l, int r)
{
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof(st));
    dist[0] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, 0});

    while (pq.size())
    {
        int u, d;
        tie(d, u) = pq.top();
        pq.pop();
        if (st[u] || d > dist[u])
            continue;
        st[u] = true;
        for (int i = head[u]; ~i; i = ne[i])
        {
            int v = edge[i], w = weight[i];
            if (st[v] || level[v] < l || level[v] > r)
                continue;
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist[1];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(head, -1, sizeof(head));
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> price[i] >> level[i];
        add(0, i, price[i]);
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++)
        {
            int x, w;
            cin >> x >> w;
            add(x, i, w);
        }
    }
    int res = 0x3f3f3f3f;
    for (int i = level[1] - m; i <= level[1]; i++)
        res = min(res, dij(i, i + m));
    cout << res << endl;
    // 起始点为 0 ,求dist[1]
}

卡图难题

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
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2010, M = N * N;

int n, m;
int head[N], ne[M], edge[M], tot = 1;
stack<int> stk;
bool ins[N];
int c[N];
int dfn[N], low[N], num, cnt;
vector<int> scc[N];

void add(int a, int b)
{
    edge[++tot] = b;
    ne[tot] = head[a], head[a] = tot;
}

void build()
{
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        string op;
        cin >> a >> b >> c >> op;
        a++, b++;
        if (op == "AND")
        {
            if (c == 1)
            { // 二者都不能为 0，为 0 时直接产生矛盾结果（如下）
                add(a, a + n);
                add(b, b + n);
            }
            else
            { // 二者中若有一个为 1，另一个一定是0。若一个为 0 ，另一个无所谓
                add(a + n, b);
                add(b + n, a);
            }
        }
        else if (op == "OR")
        {
            if (c == 1)
            { // 若有一个为 0 ，另一个必须是1
                add(a, b + n);
                add(b, a + n);
            }
            else
            { // 必须全是 0 ，有 1 直接矛盾
                add(a + n, a);
                add(b + n, b);
            }
        }
        else
        {
            if (c == 1)
            { // 两者必须不同
                add(a, b + n);
                add(a + n, b);
                add(b, a + n);
                add(b + n, a);
            }
            else
            { // 两者必须相同
                add(a, b);
                add(a + n, b + n);
                add(b, a);
                add(b + n, a + n);
            }
        }
    }
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++num;
    stk.push(u), ins[u] = true;
    for (int i = head[u]; ~i; i = ne[i])
    {
        int v = edge[i];
        if (!dfn[v]) // 未访问过，是树枝边
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (ins[v]) // 可以走到栈中的某个节点，则形成连通块
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) // 说明其是一个连通块在树上的最高点
    {
        cnt++;
        int x;
        do
        {
            x = stk.top(), ins[x] = false;
            stk.pop();
            c[x] = cnt, scc[cnt].push_back(x);
        } while (x != u);
    }
}

void output()
{
    for (int i = 1; i <= n; i++)
    {
        if (c[i] == c[i + n])
        {
            cout << "NO";
            return;
        }
    }
    cout << "YES";
}

int main()
{
    memset(head, -1, sizeof(head));
    num = cnt = 0;
    cin >> n >> m;
    build();
    for (int i = 1; i <= 2 * n; i++)
        if (!dfn[i])
            tarjan(i);
    output();
}

車的放置

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
#include <bits/stdc++.h>
using namespace std;
const int N = 210;

int n, m, t;
bool st[N][N]; // true 表示不能放置
bool vis[N];
int match[N]; // match 表示第 i 列在第几行放棋子

bool dfs(int x)
{
    for (int y = 1; y <= m; y++)
    {
        if (st[x][y] || vis[y] == true)
            continue;
        vis[y] = true;
        if (!match[y] || dfs(match[y]))
        {
            match[y] = x;
            return true;
        }
    }
    return false;
}

int main()
{
    memset(match, 0, sizeof(match));
    memset(st, 0, sizeof(st));
    cin >> n >> m >> t;
    for (int i = 1; i <= t; i++)
    {
        int a, b;
        cin >> a >> b;
        st[a][b] = true;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        memset(vis, 0, sizeof(vis));
        if (dfs(i))
            ans++;
    }
    cout << ans;
}

蚂蚁

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
#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
using ll = long long;
const int N = 110;
const double eps = 1e-6;

int n;
PII cor[2 * N];

double w[N][N];
double la[N], lb[N];
bool va[N], vb[N];
int match[N];
double nabla, upd[N];

double dist(PII a, PII b)
{
    return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}

bool dfs(int x)
{
    va[x] = 1;
    for (int y = 1; y <= n; y++)
        if (!vb[y])
        {
            if (abs(la[x] + lb[y] - w[x][y]) < eps)
            {
                vb[y] = 1;
                if (!match[y] || dfs(match[y]))
                {
                    match[y] = x;
                    return true;
                }
            }
            else
                upd[y] = min(upd[y], la[x] + lb[y] - w[x][y]);
        }
    return false;
}

void KM()
{
    for (int i = 1; i <= n; i++)
    {
        la[i] = -0x3f3f3f3f;
        lb[i] = 0;
        for (int j = 1; j <= n; j++)
            la[i] = max(la[i], w[i][j]);
    }
    for (int i = 1; i <= n; i++)
    {
        while (true)
        {
            nabla = 0x3f3f3f3f;
            memset(va, 0, sizeof(va));
            memset(vb, 0, sizeof(vb));
            for (int j = 1; j <= n; j++)
                upd[j] = 0x3f3f3f3f;
            if (dfs(i))
                break;
            for (int j = 1; j <= n; j++)
                if (!vb[j])
                    nabla = min(nabla, upd[j]);
            for (int j = 1; j <= n; j++)
            {
                if (va[j])
                    la[j] -= nabla;
                if (vb[j])
                    lb[j] += nabla;
            }
        }
    }
}

int main()
{
    cin >> n;
    for (int i = n + 1; i <= 2 * n; i++)
        cin >> cor[i].first >> cor[i].second;
    for (int i = 1; i <= n; i++)
        cin >> cor[i].first >> cor[i].second;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            w[i][j] = -dist(cor[i], cor[j + n]);
    KM();
    for (int i = 1; i <= n; i++)
        cout << match[i] << endl;
}