BZOJ 1143 [CTSC2008]祭祀river（二分图匹配）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1143
【题目大意】
给出一张有向图，问最大不连通点集，连通具有传递性
【题解】
我们将每个点拆点，拆成出点和入点，出点连接超级源点，入点连接超级汇点， 我们发现答案就是最小割的补集，而最小割等于最大流， 因此我们求这张二分图的最大流，即二分图的最大匹配。
【代码】
#include <cstdio>
#include <bitset>
#include <cstring>
using namespace std;
bitset<205>mp[205];
int x,y,n,m,Link[205],used[205];
int Dfs(int x){
for(int i=1;i<=n;i++)if(mp[x][i]&&!used[i]){
used[i]=1;
if(Link[i]==-1||Dfs(Link[i])){Link[i]=x;return 1;}
}return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
mp[x][y]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(mp[j][i])mp[j]|=mp[i];
int res=0;
memset(Link,-1,sizeof(Link));
for(int i=1;i<=n;i++){
memset(used,0,sizeof(used));
res+=Dfs(i);
}printf("%d\n",n-res);
return 0;
}
2022年9月26日 01:56
Civics is also a part of Social Studies for all Primary or Junior School students studying in Hindi medium, English medium and Urdu medium schools located in all locations of the Country. By understanding Civics subjects students can get aware of their life as good civilians and Civics also a inclusion of voting, NCERT Civics Sample Paper Class 6 volunteering, participating in group activities, and community gardening which make the students good citizens.