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)
可以用网络流或者匈牙利算法实现，前者常数较大注意卡常。

#includeusing namespace std;const int maxn=1e5+9;vector 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("%d\n",ans);}

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

文章插图
例如对于样例1
原图跑完增广路之后的边匹配情况，红色为匹配边。
接下来考虑选择第i个点之后的两轮增广情况：
第一轮如何增广的：
第二轮如何增广的：
最后图的匹配情况为：
【GCPC 2017F. Plug It In】可以发现vis数组起了关键的作用。