Jeffrey's ambition(Dinic板子题)
2022/8/29 6:23:48
本文主要是介绍Jeffrey's ambition(Dinic板子题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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's ambition(Dinic板子题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-04安装 VPrix Desktop 的系统要求-icode9专业技术文章分享
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享