原始题目
题目大意
给定两个集合，存在一些连接两个集合的边表示配合，来自不同集合的一对元素构成一个配对，求最大的配对数量
解题思路
集合内无边，所以构成二分图，求二分图的最大匹配。
解题代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define per(i, a, n) for (int i = n - 1; i >= a; --i)
#define fi first
#define se second
#define mp make_pair
#define np next_permutation
#define pb push_back
#define INF 0x3f3f3f3f
const int maxn = 1e3 + 5;
vi e[maxn];
int n, m;
bitset<maxn> v;
int fa[maxn], ans;
int dfs(int x)
{
rep(i, 0, e[x].size())
{
int y = e[x][i];
if (v[y])
continue;
v[y] = 1;
if (!fa[y] || dfs(fa[y])) {
fa[y] = x;
return 1;
}
}
return 0;
}
void init()
{
rep(i, 0, maxn) e[i].clear();
memset(fa, 0, sizeof(fa));
v.reset();
ans = 0;
}
int main()
{
ios::sync_with_stdio(false);
while (cin >> m >> n) {
init();
int a, b;
while (cin >> a >> b && a != -1) {
e[a].pb(n + b);
e[n + b].pb(a);
}
rep(i, 1, m + 1)
{
v.reset();
ans += dfs(i);
}
if (ans == 0) {
cout << "No Solution!" << endl;
continue;
}
cout << ans << endl;
rep(i, n + 1, n + n + 1)
{
if (fa[i] != 0)
cout << fa[i] << " " << i - n << endl;
}
}
}
收获与反思
寻找增广路
依次尝试给每一个左部节点 xx 寻找一个匹配的右部节点 yy 。
dfs方法。
常有两种写法
- 单标记，邻接表写法
int dfs(int x)
{
rep(i, 0, e[x].size())
{
int y = e[x][i];
if (v[y])
continue;
v[y] = 1;
if (!fa[y] || dfs(fa[y])) {
fa[y] = x;
return 1;
}
}
return 0;
}
- 双标记，数组写法
int dfs(int x){
rep(i,0,n){
if(!mmp[x][i] || v[i]) continue;
v[i] =1;
if(!fa[i] || dfs(fa[i])){
fa[i] = x;
fa[x] = i; //双标记
return 1;
}
}
return 0;
}
双标记对于访问二分图里所有点得到的匹配是实际值，单标记访问所有点得到的匹配是2倍，如果访问一个集合点则是实际值，单标记更多用于两集和已被分隔开的情况。