网路流的经典例题,会有两种需要匹配的东西,这两种东西直接可以构成一个二分图,这时候题目就会要求你求出最大匹配(水题)
//要与这道Arrange the Bulls题目区分开来。两道题同样是找匹配,但是一个是问你匹配的可能总数,而且题目是一定能构成最大匹配的,且两种东西的数量基本在20以内,要用状压dp。这道是两种要匹配的东西都很多,叫你求最大的可能的匹配是什么,要区分开来。
#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; }
以后看到有两种东西要匹配的,要往网络流这个地方想