【洛谷 P6268】【二分图】 舞会

题目

---

解题思路

先染色，确定性别
然后挑一个性别跑最大匹配
用总人数n减去最大匹配即为答案
因为邀请的人都不能一起跳过舞
如果去的人中有最大匹配中的
那么至少有一对跳过舞

---

代码

#include<iostream>
#include<cstring> 
#include<cstdio>
using namespace std;
int n,m,x,y,ans,a[1010][1010],c[1010],p[1010],g[1010],q[10100];
void dfs(int x,int s)
{c[x]=s;for (int i=1;i<=n;i++)if (a[x][i]&&!c[i])dfs(i,3-s);
}
int solve(int x)
{for (int i=1;i<=n;i++)if (!p[i]&&a[x][i]){p[i]=1;if (!g[i]||solve(g[i])){g[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);x++,y++;a[x][y]=1;a[y][x]=1;}for (int i=1;i<=n;i++)if (!c[i])  //染色dfs(i,1);for (int i=1;i<=n;i++)if (c[i]==1){memset(p,0,sizeof(p));ans+=solve(i);   //找和ta跳过舞的舞伴匹配}printf("%d",n-ans);return 0;
}