博客园同步

原题链接

前置知识：

匈牙利算法

简要题意：

求图的二分图最大独立集。

二分图最大独立集指：最大的一个点集使得每两个点都不在同一边上的这个点集的大小。

你会发现，这和 二分图最大匹配 似乎是有联系的。

给出恒等式：

二分图最大独立集 = 图的点数 - 最小点覆盖 = 图的点数 - 最大匹配。

最小点覆盖指：最小的一个点集使得每一条边至少有一个端点在该点集中。

你会发现，最小点覆盖和最大匹配本质没有区别。你选边满足边不共点，就是选点满足每边有点啊。

所以，求一遍最大匹配然后减一下即可。

• 细节

匈牙利算法的模板似乎从 $1$ ~ $n$ 扫一遍能过（尽管它题目说 的是 $0$ ~ $n-1$），但是这题不行。所以，我们要考虑 $0$ 的话，就得给 $\text{vis}$ 和 $\text{mat}$ 赋值为 $-1$.

时间复杂度：$O(n\times m)$.

实际得分：$100pts$.

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;const int N=2e3+1;inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}int n,m,T,vis[N],mat[N];
vector<int>G[N]; bool h[N];inline bool dfs(int dep,int bs) {if(vis[dep]==bs) return 0;vis[dep]=bs;for(int i=0;i<G[dep].size();i++) {int x=G[dep][i];if(mat[x]==-1 || dfs(mat[x],bs)) {mat[x]=dep;return 1;}} return 0;
}int main(){n=read(),T=read();while(T--) {int x=read(),y=read();G[x].push_back(y);} int ans=0;memset(mat,-1,sizeof(mat));memset(vis,-1,sizeof(vis));for(int i=0;i<n;i++)if(dfs(i,i)) ++ans;printf("%d\n",n-ans);	return 0;
}