OI / Graph Theory
13 minutes read (About 1981 words)

「BZOJ 4205」卡牌配对-最大流

有 $X, Y$ 两类卡牌，分别有 $n_1, n_2$ 张，每张卡牌有三个属性值：$A, B, C$。
两张卡牌能够配对，当且仅当，存在至多一项属性值使得两张卡牌该项属性值互质，且两张卡牌类别不同。
游戏的目的是最大化匹配上的卡牌组数，当然每张卡牌只能用一次。

链接

BZOJ 4205

题解

至多一项属性值使得两张卡牌该项属性值互质，即至少有两项属性不互质，这样就可以分成 A, B，B, C，A, C 三类两项不互质的。
由于 $A, B, C \leq 200$，故只会考虑到 $46$ 个质数，所以可以新建 $3 \times 46 \times 46$ 个节点来表示一类属性值中有这两种质数的卡牌，然后对于每张卡牌，枚举它的质因子（最多只有三个），然后建图跑最大流即可。

如果有一张牌 $X$ 和另一张牌 $Y$ 通过通过中间的质数对的点相连，那么就说明他们有两项属性分别有相同的质因子，即不互质，满足配对条件，而每张卡牌只能用一次，所以流量都是 $1$。

本来以为这种图 isap 得加 bfs，结果不加也就只慢了一点点，看来还是只有网格图和 Data Transmission 那样的分层图必须要加 bfs…

代码

无 bfs 标号

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「BZOJ 4205」卡牌配对 03-09-2017
 * 最大流
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template <typename T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
    iosig ? x = -x : 0;
}

inline void read(char &c) {
    while (c = read(), isspace(c) && c != -1)
        ;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        x < 0 ? (print('-'), x = -x) : 0;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void print(const char *s) {
    for (; *s; s++) print(*s);
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }

struct InputOutputStream {
    template <typename T>
    inline InputOutputStream &operator>>(T &x) {
        read(x);
        return *this;
    }

    template <typename T>
    inline InputOutputStream &operator<<(const T &x) {
        print(x);
        return *this;
    }

    ~InputOutputStream() { flush(); }
} io;
}

namespace {

using IO::io;

const int MAXN = 200;
const int MAX_NODE = 66500;
const int INF = INT_MAX >> 1;

struct Node {
    int v, f, index;

    Node(int v, int f, int index) : v(v), f(f), index(index) {}
};

struct Graph {
    typedef std::vector<Node> Vector;
    Vector edge[MAX_NODE + 1];

    inline void addEdge(const int u, const int v, const int f) {
        edge[u].push_back(Node(v, f, edge[v].size()));
        edge[v].push_back(Node(u, 0, edge[u].size() - 1));
    }

    inline Vector &operator[](const int i) { return edge[i]; }
};

struct ImprovedShortestAugmentPath {
    Graph g;

    int h[MAX_NODE + 1], gap[MAX_NODE + 1];

    inline int sap(int v, int flow, int s, int t, int n) {
        if (v == t) return flow;
        register int rec = 0;
        static int iter[MAX_NODE + 1];
        for (register int i = iter[v]; i < g[v].size(); i++) {
            Node *p = &g[v][i];
            if (p->f > 0 && h[v] == h[p->v] + 1) {
                register int ret =
                    sap(p->v, std::min(flow - rec, p->f), s, t, n);
                p->f -= ret, g[p->v][p->index].f += ret, iter[v] = i;
                if ((rec += ret) == flow || h[s] >= n) return iter[v] = 0, rec;
            }
        }
        if (!(--gap[h[v]])) h[s] = n;
        gap[++h[v]]++, iter[v] = 0;
        return rec;
    }

    inline int sap(int s, int t, int n) {
        register int ret = 0;
        for (gap[0] = n; h[s] < n;) ret += sap(s, INF, s, t, n);
        return ret;
    }

    int fac[MAXN + 1][4], pos, cnt;
    int id12[MAXN + 1][MAXN + 1];
    int id13[MAXN + 1][MAXN + 1];
    int id23[MAXN + 1][MAXN + 1];
    bool vis[MAXN + 1];

    inline void init() {
        for (register int i = 2; i <= MAXN; i++) {
            if (!vis[i]) {
                cnt++;
                for (register int j = i; j <= MAXN; j += i)
                    vis[j] = true, fac[j][++fac[j][0]] = cnt;
            }
        }
    }

    inline void solve() {
        init();
        for (register int i = 1; i <= cnt; i++)
            for (register int j = 1; j <= cnt; j++)
                id12[i][j] = ++pos, id13[i][j] = ++pos, id23[i][j] = ++pos;
        register int n, m;
        io >> n >> m;
        const int S = 0, T = n + m + pos + 1;
        for (register int x, y, z; n--;) {
            g.addEdge(S, ++pos, 1);
            io >> x >> y >> z;
            for (register int i = 1; i <= fac[x][0]; i++)
                for (register int j = 1; j <= fac[y][0]; j++)
                    g.addEdge(pos, id12[fac[x][i]][fac[y][j]], 1);
            for (register int i = 1; i <= fac[x][0]; i++)
                for (register int j = 1; j <= fac[z][0]; j++)
                    g.addEdge(pos, id13[fac[x][i]][fac[z][j]], 1);
            for (register int i = 1; i <= fac[y][0]; i++)
                for (register int j = 1; j <= fac[z][0]; j++)
                    g.addEdge(pos, id23[fac[y][i]][fac[z][j]], 1);
        }
        for (register int x, y, z; m--;) {
            g.addEdge(++pos, T, 1);
            io >> x >> y >> z;
            for (register int i = 1; i <= fac[x][0]; i++)
                for (register int j = 1; j <= fac[y][0]; j++)
                    g.addEdge(id12[fac[x][i]][fac[y][j]], pos, 1);
            for (register int i = 1; i <= fac[x][0]; i++)
                for (register int j = 1; j <= fac[z][0]; j++)
                    g.addEdge(id13[fac[x][i]][fac[z][j]], pos, 1);
            for (register int i = 1; i <= fac[y][0]; i++)
                for (register int j = 1; j <= fac[z][0]; j++)
                    g.addEdge(id23[fac[y][i]][fac[z][j]], pos, 1);
        }
        io << sap(S, T, T + 1);
    }
} task;
}

int main() {
    task.solve();
    return 0;
}

有 bfs 标号

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「BZOJ 4205」卡牌配对 03-09-2017
 * 最大流
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template <typename T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
    iosig ? x = -x : 0;
}

inline void read(char &c) {
    while (c = read(), isspace(c) && c != -1)
        ;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        x < 0 ? (print('-'), x = -x) : 0;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void print(const char *s) {
    for (; *s; s++) print(*s);
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }

struct InputOutputStream {
    template <typename T>
    inline InputOutputStream &operator>>(T &x) {
        read(x);
        return *this;
    }

    template <typename T>
    inline InputOutputStream &operator<<(const T &x) {
        print(x);
        return *this;
    }

    ~InputOutputStream() { flush(); }
} io;
}

namespace {

using IO::io;

const int MAXN = 200;
const int MAX_NODE = 66500;
const int INF = INT_MAX >> 1;

struct Node {
    int v, f, index;

    Node(int v, int f, int index) : v(v), f(f), index(index) {}
};

struct Graph {
    typedef std::vector<Node> Vector;
    Vector edge[MAX_NODE + 1];

    inline void addEdge(const int u, const int v, const int f) {
        edge[u].push_back(Node(v, f, edge[v].size()));
        edge[v].push_back(Node(u, 0, edge[u].size() - 1));
    }

    inline Vector &operator[](const int i) { return edge[i]; }
};

struct ImprovedShortestAugmentPath {
    Graph g;
    typedef Graph::Vector::iterator Iterator;
    int h[MAX_NODE + 1], gap[MAX_NODE + 1];

    inline void bfs(const int t) {
        static std::queue<int> q;
        static bool vis[MAX_NODE + 1];
        q.push(t), gap[0]++, vis[t] = true;
        while (!q.empty()) {
            register int u = q.front();
            q.pop();
            for (Iterator p = g[u].begin(); p != g[u].end(); p++)
                if (!vis[p->v])
                    gap[h[p->v] = h[u] + 1]++, vis[p->v] = true, q.push(p->v);
        }
    }

    inline int sap(int v, int flow, int s, int t, int n) {
        if (v == t) return flow;
        register int rec = 0;
        static int iter[MAX_NODE + 1];
        for (register int i = iter[v]; i < g[v].size(); i++) {
            Node *p = &g[v][i];
            if (p->f > 0 && h[v] == h[p->v] + 1) {
                register int ret =
                    sap(p->v, std::min(flow - rec, p->f), s, t, n);
                p->f -= ret, g[p->v][p->index].f += ret, iter[v] = i;
                if ((rec += ret) == flow || h[s] >= n) return iter[v] = 0, rec;
            }
        }
        if (!(--gap[h[v]])) h[s] = n;
        gap[++h[v]]++, iter[v] = 0;
        return rec;
    }

    inline int sap(int s, int t, int n) {
        register int ret = 0;
        for (bfs(t); h[s] < n;) ret += sap(s, INF, s, t, n);
        return ret;
    }

    int fac[MAXN + 1][4], pos, cnt;
    int id12[MAXN + 1][MAXN + 1];
    int id13[MAXN + 1][MAXN + 1];
    int id23[MAXN + 1][MAXN + 1];
    bool vis[MAXN + 1];

    inline void init() {
        for (register int i = 2; i <= MAXN; i++) {
            if (!vis[i]) {
                cnt++;
                for (register int j = i; j <= MAXN; j += i)
                    vis[j] = true, fac[j][++fac[j][0]] = cnt;
            }
        }
    }

    inline void solve() {
        init();
        for (register int i = 1; i <= cnt; i++)
            for (register int j = 1; j <= cnt; j++)
                id12[i][j] = ++pos, id13[i][j] = ++pos, id23[i][j] = ++pos;
        register int n, m;
        io >> n >> m;
        const int S = 0, T = n + m + pos + 1;
        for (register int x, y, z; n--;) {
            g.addEdge(S, ++pos, 1);
            io >> x >> y >> z;
            for (register int i = 1; i <= fac[x][0]; i++)
                for (register int j = 1; j <= fac[y][0]; j++)
                    g.addEdge(pos, id12[fac[x][i]][fac[y][j]], 1);
            for (register int i = 1; i <= fac[x][0]; i++)
                for (register int j = 1; j <= fac[z][0]; j++)
                    g.addEdge(pos, id13[fac[x][i]][fac[z][j]], 1);
            for (register int i = 1; i <= fac[y][0]; i++)
                for (register int j = 1; j <= fac[z][0]; j++)
                    g.addEdge(pos, id23[fac[y][i]][fac[z][j]], 1);
        }
        for (register int x, y, z; m--;) {
            g.addEdge(++pos, T, 1);
            io >> x >> y >> z;
            for (register int i = 1; i <= fac[x][0]; i++)
                for (register int j = 1; j <= fac[y][0]; j++)
                    g.addEdge(id12[fac[x][i]][fac[y][j]], pos, 1);
            for (register int i = 1; i <= fac[x][0]; i++)
                for (register int j = 1; j <= fac[z][0]; j++)
                    g.addEdge(id13[fac[x][i]][fac[z][j]], pos, 1);
            for (register int i = 1; i <= fac[y][0]; i++)
                for (register int j = 1; j <= fac[z][0]; j++)
                    g.addEdge(id23[fac[y][i]][fac[z][j]], pos, 1);
        }
        io << sap(S, T, T + 1);
    }
} task;
}

int main() {
    task.solve();
    return 0;
}
「BZOJ 1059」矩阵游戏-二分图匹配
「BZOJ 2095」Bridges-混合图欧拉回路

Comments

Follow

Tag Cloud

Algorithm CG DP Data Structure Frontend Geometry Graph Theory Hash Hexo Language Math Note Ray Tracing Rendering STL String Test

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×