Jeffrey's ambition(网络流板子题)
网路流的经典例题，会有两种需要匹配的东西，这两种东西直接可以构成一个二分图，这时候题目就会要求你求出最大匹配（水题）
//要与这道Arrange the Bulls题目区分开来。两道题同样是找匹配，但是一个是问你匹配的可能总数，而且题目是一定能构成最大匹配的，且两种东西的数量基本在20以内，要用状压dp。这道是两种要匹配的东西都很多，叫你求最大的可能的匹配是什么，要区分开来。
AC代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int MAX_N=20010;//这里要两倍且要大10的原因是有超级汇点和有两种东西
const int MAX_M=400010;//这里要有边的数量的两倍，且要有连接超级汇点的边（这里懒得算就设大了一些）
const int INF=0x3f3f3f3f;
int head[MAX_N],edge[MAX_M],nxt[MAX_M],fw[MAX_M],tot;
inline void addEdge(int u,int v,int f)
{
edge[tot]=v;//正向
fw[tot]=f;
nxt[tot]=head[u];
head[u]=tot++;
edge[tot]=u;//反向
fw[tot]=0;
nxt[tot]=head[v];
head[v]=tot++;
}
// 深度、当前弧
int dep[MAX_N], cur[MAX_N];
// 生成分层图
bool bfs(int s, int t) {
memset(dep, 0, sizeof(dep));
memcpy(cur, head, sizeof(cur));
std::queue<int> que;
que.emplace(s);
dep[s] = 1;
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = head[u]; ~i; i =nxt[i])
if (fw[i] && !dep[edge[i]]) {
dep[edge[i]] = dep[u] + 1;
que.emplace(edge[i]);
}
}
return dep[t];
}
// 修改流量，使用当前弧优化
int dfs(int u, int t, int f) {
if (!f || u == t)
return f;
int flow = 0;
for (int i = cur[u]; flow < f && ~i; i = nxt[i]) {
cur[u] = i;
if (fw[i] && dep[edge[i]] == dep[u] + 1) {
int tmp = dfs(edge[i], t, std::min(f - flow, fw[i]));
fw[i] -= tmp;
fw[i^1] += tmp;
flow += tmp;
}
}
return flow;
}
// Dinic主方法
int dinic(int s, int t) {
int ans = 0;
while (bfs(s, t))
ans += dfs(s, t, INF);
return ans;
}
int main(void)
{
memset(head,-1,sizeof(head));
int N,M;
scanf("%d %d",&N,&M);
int S=N+M+1,T=N+M+2;
for(int i=1;i<=N;i++)
{
int x;scanf("%d",&x);
for(int j=0;j<x;j++)
{
int y;scanf("%d",&y);
addEdge(i,y+N,1);
}
}
for(int i=1;i<=N;i++)addEdge(S,i,1);
for(int j=1;j<=M;j++)addEdge(j+N,T,1);
cout<<M-dinic(S,T)<<endl;
return 0;
}
以后看到有两种东西要匹配的，要往网络流这个地方想
标签：Jeffrey,fw,int,MAX,head,tot,dep,ambition,Dinic From： https://www.cnblogs.com/WUTONGHUA02/p/16634616.html