P1330 封锁阳光大学
二分图
:在一张图中,如果能够把全部的点分到两个集合中,保证两个集合内部没有任何边 ,图中的边只存在于两个集合之间,这张图就是二分图
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 100010, M = 200010;
int head[N], to[M], ne[M], tot, color[N];
void add(int u, int v) {//链式前向星
to[tot] = v, ne[tot] = head[u], head[u] = tot++;
}
int cnt[3],ans;
bool dfs(int u, int c) {
color[u] = c,cnt[c]++;//染色,0:1:白 2:黑
for (int i = head[u]; ~i; i = ne[i]) {
int j = to[i];
if (!color[j]) {
if (!dfs(j, 3 - c))
return false;//染色未发生冲突
}
else if (color[j] == c)
return false;//染色发生冲突
}
return true;
}
int main() {
memset(head, -1, sizeof head);
memset(color, 0, sizeof color);
int n, m;
scanf("%d%d", &n, &m);
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);//构建无向图
}
bool flag = true;
for (int i = 1; i <= n; i++) {
//计算每个连通块需要几个河蟹
cnt[2]=cnt[1]=0;
if (!color[i]) {//遍历一个连通图
if (!dfs(i, 1)) {
flag = false;
break;
}
}
ans+=min(cnt[1],cnt[2]);//ans+=每个连通图至少需要几个河蟹
}
if(flag)cout<<ans;
else cout<<"Impossible";
return 0;
}
P3386 【模板】二分图最大匹配
匈牙利算法
解决二分图最大匹配问题
最大匹配
:一个图的所有匹配中,所含匹配边数最多的匹配,称为最大匹配
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 510, M = 100010;
int head[N], to[M], ne[M], tot, match[N];
bool st[N];
void add(int u, int v) {
to[tot] = v, ne[tot] = head[u], head[u] = tot++;
}
bool find(int x) {
for (int i = head[x]; ~i; i = ne[i]) {
int j = to[i];
if (!st[j]) {
st[j] = true;
if (match[j] == 0 || find(match[j])) {
match[j] = x;
return true;
}
}
}
return false;
}
int main() {
memset(head, -1, sizeof head);
int n1, n2, m;
scanf("%d%d%d", &n1, &n2, &m);
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
int res = 0;
for (int i = 1; i <= n1; i++) {
memset(st, false, sizeof st);
if (find(i)) res++;
}
printf("%d", res);
return 0;
}