BZOJ 1143: [CTSC2008]祭祀river 最大独立集

题目链接:

http://www.lydsy.com/JudgeOnline/problem.php?id=1143

题解:

给你一个DAG,求最大的顶点集,使得任意两个顶点之间不可达。

把每个顶点v拆成v和v',对于边u,v,建成(u,v'),得到一个二分图。

先对二分图floyd求闭包,然后求二分图的最大独立集就可以了。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; const int maxn = 111; int mat[maxn][maxn];
int vis[maxn], lef[maxn];
int n, m; void init() {
memset(mat, 0, sizeof(mat));
memset(lef, 0, sizeof(lef));
} bool match(int u) {
for (int i = 1; i <= n; i++) {
if (mat[u][i]&&!vis[i]) {
vis[i] = 1;
if (!lef[i] || match(lef[i])) {
lef[i] = u;
return true;
}
}
}
return false;
} int main() {
while (scanf("%d%d", &n, &m) == 2 && n) {
init();
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
mat[u][v] = 1;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (mat[i][k] && mat[k][j]) {
mat[i][j] = 1;
}
}
}
}
for (int i = 1; i <= n; i++) {
memset(vis, 0, sizeof(vis));
match(i);
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (lef[i] != 0) cnt++;
}
printf("%d\n", n - cnt);
}
return 0;
}
上一篇:stl::map之const函数访问


下一篇:28. Triangle && Pascal's Triangle && Pascal's Triangle II