题目链接: https://acm.uestc.edu.cn/problem/cxxshou-zhu-dai-tu/description
分析:
这道题题意有点模糊,绕来绕去。
仔细看并抽象出来,其实就是,任意边至少有一个顶点属于集合,求集合元素数的最小值。
在图论中,这个叫做最小顶点覆盖。而在二分图中,最小顶点覆盖的值等于最大匹配的值。我们又知道,二分图最大匹配的值就是最大流的值。
所以设一个超级源点连所有左边的点,一个超级汇点连所有右边的点,左右两边的点按照题目的意思连接,边容量为1,然后跑一遍最大流即可。
不知道有没有卡其他算法,无脑Dinic
代码:
#include <iostream> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <cstdio> #include <iomanip> using namespace std; const int INF = 0x3f3f3f3f; /////////////////////////// const int MAX_V=100005; struct edge { int to,cap,rev; }; vector<edge> G[MAX_V]; int level[MAX_V]; int iter[MAX_V]; void add_edge(int from, int to, int cap) { G[from].push_back((edge){to, cap, G[to].size()}); G[to].push_back((edge){from, 0, G[from].size()-1}); } void bfs(int s) { memset(level,-1,sizeof(level)); queue<int> que; level[s] = 0; que.push(s); while(!que.empty()) { int v=que.front();que.pop(); for(int i=0;i<G[v].size();++i) { edge e=G[v][i]; if(e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; que.push(e.to); } } } } int dfs(int v,int t,int f) { if(v==t)return f; for(int &i=iter[v];i < G[v].size();++i) { edge &e=G[v][i]; if(e.cap > 0 && level[v] < level[e.to]) { int d=dfs(e.to, t, min(f, e.cap)); if(d > 0) { e.cap -=d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s,int t) { int flow=0; for(;;) { bfs(s); if(level[t] < 0) { return flow; } memset(iter,0,sizeof(iter)); int f; while((f = dfs(s, t ,INF)) > 0) { flow+=f; } } } //////// int main() { ios::sync_with_stdio(false); cin.tie(0); int a,b,m,l,r; cin>>a>>b>>m; int s=a+b+1;int t=s+1; for(int i=0;i<m;++i) { cin>>l>>r; add_edge(l,a+r,1); } for(int i=1;i<=a;++i) { add_edge(s,i,1); } for(int i=a+1;i<=a+b;++i) { add_edge(i,t,1); } cout<<max_flow(s,t)<<endl; return 0; }