[HDU] 1068 Girls and Boys(二分图最大匹配)

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1068

本题求二分图最大独立点集。因为最大独立点集=顶点数-最大匹配数。所以转化为求最大匹配。因为没有给出男女,所以每个人都用了两遍,所以结果应该除以2。

 #include<cstdio>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<stdbool.h>
#include<time.h>
#include<stdlib.h>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
using namespace std;
#define clr(x,y) memset(x,y,sizeof(x))
#define sqr(x) ((x)*(x))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define LL long long
#define INF 0x3f3f3f3f
#define A first
#define B second
#define PI 3.14159265358979323
const int N=+;
int n,m,f[N],g[N][N],link[N]; void init()
{
clr(f,);
clr(g,);
clr(link,-);
} bool find(int x)
{
for(int i=;i<n;i++) {
if(!f[i] && g[x][i]) {
f[i]=;
if(link[i]==- || find(link[i])) {
link[i]=x;
return true;
}
}
} return false;
} int hungary()
{
int ans=;
for(int i=;i<n;i++) {
clr(f,);
if(find(i)) ans++;
}
return ans;
} int main()
{
int u,v; while(~scanf("%d",&n)) {
init();
for(int i=;i<n;i++) {
scanf("%d: (%d)",&u,&m);
while(m--){
scanf("%d",&v);
g[u][v]=;
}
}
printf("%d\n",n-hungary()/);
} return ;
}
上一篇:mysql修改字段的语句写法


下一篇:Spring对Quartz的封装实现简单需注意事项