caioj 1125
二分图最小点覆盖模板题，同样使用最大流dinic做
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 20000 + 10, MAXM = 200000 + 40000 + 10, INF = 2147483647;
int en, n, m, k;
struct data {int v, cap, flow;}ed[MAXM];
vector<int> G[MAXN];
int s, t, d[MAXN], vis[MAXN], cur[MAXN];
void ins(int u, int v, int c) {
ed[en] = (data){v, c, 0}, G[u].push_back(en++);
ed[en] = (data){u, 0, 0}, G[v].push_back(en++);
}
void clean() {
en = 0, s = n + m + 1, t = n + m + 2;
for (int i = 0; i <= n + m + 2; i++) G[i].clear();
}
bool bfs() {
queue<int> q;
for (int i = 0; i <= n + m + 2; i++) d[i] = INF, vis[i] = false;
q.push(s), d[s] = 0, vis[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < (int)G[u].size(); i++) {
int v = ed[G[u][i]].v, cap = ed[G[u][i]].cap, flow = ed[G[u][i]].flow;
if (!vis[v] && cap > flow) {
vis[v] = true, d[v] = d[u] + 1;
q.push(v);
}
}
}
return vis[t];
}
int dfs(int u, int a) {
if (u == t) return a;
if (a == 0) return 0;
int retflow = 0;
for (int &i = cur[u]; i < (int)G[u].size(); i++) {
int v = ed[G[u][i]].v, cap = ed[G[u][i]].cap, flow = ed[G[u][i]].flow;
if (d[v] == d[u] + 1) {
if (cap > flow) {
int f = dfs(v, min(a, cap - flow));
if (f > 0) {
a -= f, retflow += f, ed[G[u][i]].flow += f, ed[G[u][i] ^ 1].flow -= f;
if (a == 0) break;
}
}
}
}
return retflow;
}
int dinic() {
int flow = 0;
while (bfs()) {
for (int i = 0; i <= n + m + 2; i++) cur[i] = 0;
flow += dfs(s, INF);
}
return flow;
}
void solve() {
clean();
for (int i = 1; i <= n; i++) ins(s, i, 1);
for (int i = 1; i <= n; i++) ins(i + n, t, 1);
for (int u, v, i = 1; i <= k; i++) {
scanf("%d%d", &u, &v);
ins(u, v + n, 1);
}
printf("%d\n", dinic());
}
int main() {
while (scanf("%d%d%d", &n, &m, &k) == 3) solve();
return 0;
}
题目描述
【题目描述】
X集合有n个点（编号1，2，3，……n），
Y集合有m个点（编号1，2，3，……m），
有k条边（任意一条边的两个端点，一个来自X集合，一个来自Y集合）
如果选中一个点（可以来自X集合或Y集合）就是燃烧掉所有与该点相连的边。
问：至少选中多少个点，可以摧毁所有边（也就是k条边）
【输入】
第一行三个整数n, m，k( 0< n, m < 10000，0< k < 100000）。
下来k行，每行两个整数 x，y，表示一条边，连接X集合中x点和Y集合的y点。
【输出】一个整数，为最少选中的点数目。
输入：
4 5
8
1 3
2 1
2 2
2 4
3 3
4 3
4 4
4 5
输出：
3
