UOJ#79. 一般图最大匹配
? 解题记录 ? ? UOJ ? ? 带花树 ?    2018-07-01 11:02:38    562    0    0

### 样例一

#### input

10 20
9 2
7 6
10 8
3 9
1 10
7 1
10 9
8 6
8 2
8 1
3 1
7 5
4 7
5 9
7 8
10 4
9 1
4 8
6 3
2 5

#### output

5
9 5 6 10 2 3 8 7 1 4

### 样例二

#### input

5 4
1 5
4 2
2 1
4 3

#### output

2
2 1 4 3 0

### 限制与约定

1n5001≤n≤5001m1247501≤m≤124750

## 一般图最大匹配

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e3 + 5;
const int maxm = 124750 + 5;
int n, m, u, v;
struct edge {
int v, next;
}e[maxm << 1];

void adde(const int &u, const int &v) {
}

namespace DSU {
int fa[maxn];
void init(int x) {for(register int i = 1; i <= x; ++i) fa[i] = i;}
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void combine(int a, int b) {fa[find(a)] = find(b);}
}

int type[maxn], match[maxn], pre[maxn], tid[maxn], id;

int LCA(int u, int v) {
for(++id;;swap(u, v))
if(u) {
u = DSU::find(u);
if(tid[u] == id) return u;
else tid[u] = id, u = pre[match[u]];
}
}

void Bloom(int u, int v, int lca, queue<int > * q) {
while(DSU::find(u) != lca) {
pre[u] = v, v = match[u];
if(DSU::find(u) == u) DSU::fa[u] = lca;
if(DSU::find(v) == v) DSU::fa[v] = lca;
if(type[v] == 1) type[v] = 0, q -> push(v);
u = pre[v];
}
}

bool AGM(int u) { //  augmentation;
DSU::init(n);
memset(type, -1, sizeof(int) * (n + 1));
memset(pre, 0, sizeof(int) * (n + 1));
queue<int > q; q.push(u);
while(!q.empty()) {
int u = q.front();
q.pop();
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(DSU::find(u) == DSU::find(v)) continue;
if(type[v] == -1) {
if(!match[v]) {
while(u) {
int t = match[u];
match[match[v] = u] = v;
u = pre[v = t];
}
return 1;
}
type[v] = 1, pre[v] = u;
type[match[v]] = 0, q.push(match[v]);
} else if(type[v] == 0) {
int lca = LCA(u, v);
Bloom(u, v, lca, &q);
Bloom(v, u, lca, &q);
}
}
}
return 0;
}

int ans = 0;

int main() {
scanf("%d%d", &n, &m);
for(register int i = 1; i <= m; ++i)
for(register int i = 1; i <= n; ++i)
if(!match[i]) ans += AGM(i);
printf("%d\n", ans);
for(register int i = 1; i <= n; ++i)
printf("%d ", match[i]);
return 0;
} 

#include
#include
#include
#include
using namespace std;
const int maxn = 1e3 + 5;
const int maxm = 124750 + 5;
int n, m, u, v;
struct edge {
int v, next;
}e[maxm << 1];

void adde(const int &u, const int &v) {
}

namespace DSU {
int fa[maxn];
void init(int x) {for(register int i = 1; i <= x; ++i) fa[i] = i;}
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void combine(int a, int b) {fa[find(a)] = find(b);}
}

int type[maxn], match[maxn], pre[maxn], tid[maxn], id;

int LCA(int u, int v) {
for(++id;;swap(u, v))
if(u) {
u = DSU::find(u);
if(tid[u] == id) return u;
else tid[u] = id, u = pre[match[u]];
}
}

void Bloom(int u, int v, int lca, queue<int > * q) {
while(DSU::find(u) != lca) {
pre[u] = v, v = match[u];
if(DSU::find(u) == u) DSU::fa[u] = lca;
if(DSU::find(v) == v) DSU::fa[v] = lca;
if(type[v] == 1) type[v] = 0, q -> push(v);
u = pre[v];
}
}

bool AGM(int u) {
DSU::init(n);
memset(type, -1, sizeof(int) * (n + 1));
memset(pre, 0, sizeof(int) * (n + 1));
queue q; q.push(u);
while(!q.empty()) {
int u = q.front();
q.pop();
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(DSU::find(u) == DSU::find(v)) continue;
if(type[v] == -1) {
if(!match[v]) {
while(u) {
int t = match[u];
match[match[v] = u] = v;
u = pre[v = t];
}
return 1;
}
type[v] = 1, pre[v] = u;
type[match[v]] = 0, q.push(match[v]);
} else if(type[v] == 0) {
int lca = LCA(u, v);
Bloom(u, v, lca, &q);
Bloom(v, u, lca, &q);
}
}
}
return 0;
}

int ans = 0;

int main() {
scanf("%d%d", &n, &m);
for(register int i = 1; i <= m; ++i)
for(register int i = 1; i <= n; ++i)
if(!match[i]) ans += AGM(i);
printf("%d\n", ans);
for(register int i = 1; i <= n; ++i)
printf("%d ", match[i]);
return 0;
} 

562 人读过

0 条评论