二分图裸题，可以拿最大流怼。
先来一段匈牙利算法AC代码，关于匈牙利算法的说明看其他博客去，这里重点是网络流。。。首先你要有前置技能
1，会求最大流(dinic, isap， EK, FF 随便会一个)。
2，知道什么是二分图匹配
#include <bits/stdc++.h> using namespace std;
const int MAXN = ;
const int INF = 0x3F3F3F3F; int n, m, first[MAXN], sign; struct Edge {
int to, w, next;
} edge[MAXN * MAXN]; int link[MAXN], vis[MAXN]; inline void init() {
for(int i = ; i <= n; i++ ) {
first[i] = -;
}
sign = ;
} inline void add_edge(int u, int v, int w) {
edge[sign].to = v;
edge[sign].w = w;
edge[sign].next = first[u];
first[u] = sign ++;
} bool match(int x) {
for(int i = first[x]; ~i; i = edge[i].next) {
int to = edge[i].to;
if(!vis[to]) {
vis[to] = ;
if(!link[to] || match(link[to])) {
link[to] = x;
return ;
}
}
}
return ;
} int main()
{
while(~scanf("%d %d", &n, &m)) {
init();
int u, v;
while(~scanf("%d %d", &u, &v)) {
if(u == - && v == -) {
break;
}
add_edge(u, v, );
}
memset(link, , sizeof(link));
int ans = ;
for(int i = ; i <= n; i++ ) {
memset(vis, , sizeof(vis));
if(match(i)) {
ans ++;
}
}
if(ans) {
printf("%d\n", ans);
vector<pair<int, int> > vec;
for(int i = n + ; i <= n + m; i++ ) {
if(link[i]) {
vec.push_back(make_pair(link[i], i));
}
}
auto cmp = [](pair<int, int> &a, pair<int, int> &b) {
return a.first < b.first;
};
sort(vec.begin(), vec.end(), cmp);
for(int i = ; i < vec.size(); i++ ) {
printf("%d %d\n", vec[i].first, vec[i].second);
}
} else {
puts("No Solution!");
}
}
return ;
}
网络流的解法。
用网络流写二分图是因为我KM算法了学吐了。。。 然后发现网络流的dinic在二分图中具有着优秀的复杂度。学习一波。对于无权二分图，我们可以让起边权为1，虚拟出源点，源点引出一系列权值1的边指向集合A的所有点。集合B的所有点引出一条权值1的边指向汇点。然后直接dinic最大流即可。然后一个问题就是如何把匹配关系找出来。这部分看注释。另外这题又spacial judge。匹配结果可行集合，不需要与案例一样。
关于匹配点这么获得：
网络流解二分图，正向弧和反向弧权要么是1，要么是0 .而且集合只有两个。没有普通网络流中间的一堆点。集合B中边权是1，且不指向t的点。就是集合A中他的匹配点。(想明白后感觉我又废话了，其他题解都没解释，这部分卡了我十几分钟囧。。。)
#include <bits/stdc++.h> using namespace std;
const int maxn = ;
const int maxm = 1e4 + ;
const int inf = 0x7fffffff;
typedef long long LL; int s, t, n, m; struct Edge {
int to, w, next;
} edge[maxm]; int first[maxn], cur[maxn], sign, dist[maxn]; void init() {
for(int i = ; i <= n + m + ; i ++ ) {
first[i] = -;
}
sign = ;
} void add_edge(int u,int v,int w) {
edge[sign].to = v, edge[sign].w = w;
edge[sign].next = first[u], first[u] = sign++; edge[sign].to = u, edge[sign].w = ;
edge[sign].next = first[v], first[v] = sign++;
} bool bfs(int s,int t) {
memset(dist, -, sizeof(dist));
queue<int>que;
que.push(s), dist[s] = ;
while(!que.empty()) {
int now = que.front();
que.pop();
if(now == t) {
return ;
}
for(int i = first[now]; ~i; i = edge[i].next) {
int to = edge[i].to, ww = edge[i].w;
if(dist[to] == - && ww > ) {
dist[to] = dist[now] + ;
que.push(to);
}
}
}
return ;
} int dfs(int s, int t, int max_flow) {
if(s == t) {
return max_flow;
}
for(int &i = cur[s]; ~i; i = edge[i].next) {
int to = edge[i].to, ww = edge[i].w;
if(dist[to] == dist[s] + && ww > ) {
int flow = dfs(to, t, min(max_flow, ww));
if(flow > ) {
edge[i].w -= flow;
edge[i ^ ].w += flow;
return flow;
}
}
}
return ;
} int dinic(int s, int t) {
int ans = ;
while(bfs(s, t)) {
for(int i = ; i <= t; i ++ ) {
cur[i] = first[i];
}
ans += dfs(s, t, inf);
}
return ans;
} int main() { while(~scanf("%d %d", &n, &m)) {
init();
s = , t = n + m + ;
for(int i = ; i <= n; i++ ) {
add_edge(, i, );
}
for(int i = n + ; i <= n + m; i++ ) {
add_edge(i, t, );
}
int u, v;
while(~scanf("%d %d", &u, &v)) {
if(u == - && v == -) {
break;
}
add_edge(u, v, );
}
int ans = dinic(s, t);
printf("%d\n", ans);
if(ans) {
for(int i = n + ; i <= n + m; i++ ) {
for(int j = first[i]; ~j; j = edge[j].next) {
if(edge[j].w == && edge[j].to != t) {
printf("%d %d\n", edge[j].to, i);
}
}
} } else {
puts("No Solution!");
}
}
return ;
}
一个封装的Dinic
#include <bits/stdc++.h>
using namespace std;
struct Dinic {
static const int MAXN = 1e4 + ;
static const int MAXM = 1e5 + ;
static const int INF = 0x3f3f3f3f;
int n, m, s, t;
int first[MAXN], cur[MAXN], dist[MAXN], sign;
struct Node {
int to, flow, next;
} edge[MAXM * ];
inline void init(int start, int vertex, int ss, int tt) {
n = vertex, s = ss, t = tt;
for(int i = start; i <= n; i++ ) {
first[i] = -;
}
sign = ;
}
inline void addEdge(int u, int v, int flow) {
edge[sign].to = v, edge[sign].flow = flow, edge[sign].next = first[u];
first[u] = sign++;
}
inline void add_edge(int u, int v, int flow) {
addEdge(u, v, flow);
addEdge(v, u, );
}
inline int dinic() {
int max_flow = ;
while(bfs(s, t)) {
for(int i = ; i <= n; i++ ) {
cur[i] = first[i];
}
max_flow += dfs(s, INF);
}
return max_flow;
}
bool bfs(int s, int t) {
memset(dist, -, sizeof(dist));
queue<int>que;
que.push(s), dist[s] = ;
while(!que.empty()) {
int now = que.front();
que.pop();
if(now == t) {
return ;
}
for(int i = first[now]; ~i; i = edge[i].next) {
int to = edge[i].to, flow = edge[i].flow;
if(dist[to] == - && flow > ) {
dist[to] = dist[now] + ;
que.push(to);
}
}
}
return ;
}
int dfs(int now, int max_flow) {
if(now == t) {
return max_flow;
}
for(int &i = cur[now]; ~i; i = edge[i].next) {
int to = edge[i].to, flow = edge[i].flow;
if(dist[to] == dist[now] + && flow > ) {
int next_flow = dfs(to, min(flow, max_flow));
if(next_flow > ) {
edge[i].flow -= next_flow;
edge[i ^ ].flow += next_flow;
return next_flow;
}
}
}
return ;
}
///显示二分图匹配结果,n,m分别是两个集合的大小
void show(int n, int m) {
for(int i = n + ; i <= n + m; i++ ) {
for(int j = first[i]; ~j; j = edge[j].next) {
if(edge[j].flow == && edge[j].to != t) {
printf("%d %d\n", edge[j].to, i);
}
}
}
}
} cwl;
int main() {
int n, m;
int u, v;
scanf("%d %d", &n, &m);
cwl.init(, n + m + , , n + m + );
for(int i = ; i <= n; i++ ) {
cwl.add_edge(, i, );
}
for(int i = n + ; i <= n + m; i++ ) {
cwl.add_edge(i, n + m + , );
}
while(~scanf("%d %d", &u, &v)) {
if(u == - && v == -) {
break;
}
cwl.add_edge(u, v, );
}
int ans = cwl.dinic();
printf("%d\n", ans);
if(ans) {
cwl.show(n, m);
} else {
puts("No Solution!");
}
return ;
}