CF387D
发表算法5 分钟读完 (大约705个字)

CF387D

题意分析

操作最少的次数，构成有趣图，注意无重边，有向边。

  • 操作分为加边和删边。
  • 有趣图定义
    • 有一个中心，满足此点有自环，且与其他结点有双向边。
    • 除中心点外的结点，满足出度 = 入度 = 2。
阅读更多
匹配：模板
发表算法5 分钟读完 (大约715个字)

匹配：模板

UOJ78 二分图最大匹配（DFS - KM）

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
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

const int N = 550;

int match[N], g[N][N], vis[N], link[N];
int n, m, e, tag, ans = 0;

bool dfs(int u) {
    
    for(int v=1; v<=m; ++v) {
        if(!g[u][v] or vis[v] == tag) continue;
        vis[v] = tag;
        if(!match[v] or dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}
int main() {
    
    scanf("%d%d%d", &n, &m, &e);
    for(int i=1, u, v; i<=e; ++i) {
        scanf("%d%d", &u, &v);
        g[u][v] = true;
    }
    
    for(int i=1; i<=n; ++i) {
        tag = i;
        if(dfs(i)) ++ans;
    }
    
    printf("%d\n", ans);
    for(int i=1; i<=m; ++i) link[match[i]] = i;
    
    for(int i=1; i<=n; ++i) printf("%d ", link[i]);
    
    return 0;
}

UOJ79 一般图最大匹配（带花树）

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 550;
int fa[N], match[N], pre[N], vis[N];
int tag = 0, n, m, ans = 0;
int flag[N];
bool g[N][N];
queue<int> q;

void clear(queue<int> &q) {
    queue<int> empty;
    swap(q, empty);
}
int belong(int u) {
    return fa[u] == u ? u : fa[u] = belong(fa[u]);
}

void path(int u) {
    while(u) {
        int v = match[pre[u]];
        match[u] = pre[u];
        match[pre[u]] = u;
        u = v;
    }
}
int lca(int u, int v) {
    ++tag;
    u = belong(u);
    v = belong(v);
    while(vis[u] != tag) {
        vis[u] = tag;
        u = belong(pre[match[u]]);
        if(v) swap(u, v);
    }
    return u;
}
void connect(int u, int v, int root) {
    while(belong(u) != root) {
        pre[u] = v;
        v = match[u];
        if(flag[v] == 2) {
            q.push(v);
            flag[v] = 1;
        }
        if(belong(u) == u) fa[u] = root;
        if(belong(v) == v) fa[v] = root;
        u = pre[v];
    }
}
bool bfs(int u) {
    
    memset(flag, 0, sizeof flag);
    memset(pre, 0, sizeof pre);
    for(int i=1; i<=n; ++i) fa[i] = i;
    
    clear(q);
    q.push(u);
    flag[u] = 1;
    
    while(!q.empty()) {
        u = q.front();
        q.pop();
        for(int v=1; v<=n; ++v) {
            if(!g[u][v]) continue;
            if(flag[v] == 0) {
                pre[v] = u;
                if(match[v] == 0) {
                    path(v);
                    return true;
                }
                q.push(match[v]);
                flag[v] = 2;
                flag[match[v]] = 1;
            } else {
                if(flag[v] == 2) continue;
                if(belong(u) == belong(v)) continue;
                int root = lca(u, v);
                connect(u, v, root);
                connect(v, u, root);
            }
        }
    }
    return false;
}
int main() {
    
    scanf("%d%d", &n, &m);
    for(int i=1, u, v; i<=m; ++i) {
        scanf("%d%d", &u, &v);
        g[u][v] = g[v][u] = true;
    }
    
    for(int i=1; i<=n; ++i) 
        if(match[i] == 0 and bfs(i)) ++ans;
    
    printf("%d\n", ans);
    for(int i=1; i<=n; ++i) printf("%d ", match[i]);
     
    return 0;
}

UOJ80 二分图最大权匹配（BFS - KM）

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 <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 440;
const LL INF = 0x3f3f3f3f3f3f3f3f;

bool vis[N];
int pre[N], link[N], res[N];
int n, m, e;
LL g[N][N], lx[N], ly[N], d[N], ans = 0;

void bfs(int k) {
    
    int x, y = 0;
    LL min1 = INF, delta;
    memset(vis, false, sizeof vis);
    memset(pre, 0, sizeof pre);
    memset(d, 0x3f, sizeof d);
    link[y] = k;
    
    do {
        x = link[y], delta = INF, vis[y] = true;
        for(int i=1; i<=m; ++i) {
            if(!vis[i]) {
                if(d[i] > lx[x] + ly[i] - g[x][i]) {
                    d[i] = lx[x] + ly[i] - g[x][i];
                    pre[i] = y;
                }
                if(delta > d[i]) delta = d[i], min1 = i;
            }
        }
        for(int i=0; i<=m; ++i)
            if(vis[i]) lx[link[i]] -= delta, ly[i] += delta;
            else d[i] -= delta;
        y = min1;
    } while(link[y]);
    while(y) link[y] = link[pre[y]], y = pre[y];
}

int main() {
    
    scanf("%d%d%d", &n, &m, &e);
    m = max(n, m);
    for(int i=1; i<=e; ++i) {
        int u, v; LL w;
        scanf("%d%d%lld", &u, &v, &w);
        g[u][v] = w;
        lx[u] = max(lx[u], w);
    }
    
    for(int i=1; i<=n; ++i) bfs(i);
    
    for(int i=1; i<=m; ++i) {
        if(!g[link[i]][i]) continue;
        ans += g[link[i]][i];
        res[link[i]] = i;
    }
    printf("%lld\n", ans);
    for(int i=1; i<=n; ++i) printf("%d ", res[i]);
    
    return 0;
}
关注我

分类

标签

AI2
Aplayer1
Butterfly1
DAG1
DFS3
GitHub1
Hexo2
LCA1
PB_DS1
SSH1
STL2
二分图2
动态规划3
匹配2
单调队列2
博客2
双指针1
图书馆4
图论4
小说7
尺取法1
平衡树1
排序2
数学1
数据结构1
数论3
最小割1
最短路4
树1
游记1
码风1
算法25
网络流5
记忆化搜索4
部署1
随感2
随笔1

最新文章

归档

×