(GCPC 2017) F. Plug It In

阅读: 评论:0

(GCPC 2017) F. Plug It In

(GCPC 2017) F. Plug It In

题意有m个插座,有n个电器,m个插座和n个用电器之间有k条边。
插座和插座之前没有边,电器和电器之间没有边。一个插座插一个电器。
是个二分图。
现在可以选择其中1个插座使它可以插3个电器,问最多多少电器可以通上电。

这题其实就是查找二分图的最大匹配。
但存在1个插座可以插3个电器的情况,也许会容易思考到网络流,或者把1个点拆成3个点。
无论如何,跑一次二分图最大匹配的最优时间复杂度是 O ( n m ) O(sqrt n m) O(n ​ m),如果枚举每一个点,那么总的时间复杂度是 O ( n m n ) O(nm sqrt n) O(nmn ​) 无法通过

细思考一下二分图匹配的增广路算法,例如现在选择第 i i i个点使它变成可以插3个电器。
网络流:
从原点到第 i i i个点的流量变成3,继续在残余图上寻找增广路
匈牙利等朴素增广路算法:
“复制”第 i i i个点,使其变为 n + 1 , n + 2 n+1,n+2 n+1,n+2,然后再对这两个点找两次增广路。

从而发现网络流和匈牙利算法都可以在“每个插座匹配一个电气”的基础上继续匹配。
所以我们可以保存下插座变化前的图的匹配状态(或者网络流的流量状态,即残余图),然后添加节点(或网络流中边的流量),继续增广。
此时,每一轮重新增广,只会多寻找2次增广路,遍历全图最多两次,所以枚举每一个点时间复杂度变成 O ( m + n ) O(m+n) O(m+n)
总时间复杂度为
O ( n m ) O(nm) O(nm)
可以用网络流或者匈牙利算法实现,前者常数较大注意卡常。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
vector<int> g[maxn];
int link[maxn],save[maxn];//
char vis[maxn];
int dfs(int x){for(int i:g[x]){if(vis[i]) continue;vis[i]=1;if(link[i]==0||dfs(link[i])) return link[i]=x,1;}return 0;
}
int main(){int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int u,v,i=1;i<=k;i++){scanf("%d%d",&u,&v);g[u].push_back(v);}int base=0,ans;for(int i=1;i<=n;i++){memset(vis,0,m+3);ans+=dfs(i);}base=ans;memcpy(save,link,sizeof(int)*(m+3));//save存下图匹配的状态for(int i=1;i<=n;i++){memcpy(link,save,sizeof(int)*(m+3));//读取图改变之前的匹配状态memset(vis,0,m+3);int tv=0;for(int j=1;j<=2;j++) tv+=dfs(i);//这里在原来的点上增广ans=max(ans,base+tv);}printf("%dn",ans);
}

图中是是用了类似匈牙利算法去跑这个匹配,可能让人寻味的即是第34行中,为什么可以在第i个点上直接继续寻找增广路。

例如对于样例1

原图跑完增广路之后的边匹配情况,红色为匹配边。
接下来考虑选择第i个点之后的两轮增广情况:
第一轮如何增广的:

第二轮如何增广的:

最后图的匹配情况为:

可以发现vis数组起了关键的作用。

本文发布于:2024-02-02 09:00:58,感谢您对本站的认可!

本文链接:https://www.4u4v.net/it/170683565842737.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

标签:GCPC   Plug
留言与评论(共有 0 条评论)
   
验证码:

Copyright ©2019-2022 Comsenz Inc.Powered by ©

网站地图1 网站地图2 网站地图3 网站地图4 网站地图5 网站地图6 网站地图7 网站地图8 网站地图9 网站地图10 网站地图11 网站地图12 网站地图13 网站地图14 网站地图15 网站地图16 网站地图17 网站地图18 网站地图19 网站地图20 网站地图21 网站地图22/a> 网站地图23