(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
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("%d\n",ans);
}

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

例如对于样例1

原图跑完增广路之后的边匹配情况，红色为匹配边。

接下来考虑选择第i个点之后的两轮增广情况：

第一轮如何增广的：

第二轮如何增广的：

最后图的匹配情况为：

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