这道题要先判断图是不是二分图,如果不是的话,就直接输出No,是的话就求最大匹配,
建边是双向的所以要/2
判断二分图:对点进行染色,如果A与B认识,A,B的颜色要不同,
如果出现颜色相同的就矛盾了,就不是二分图
#include<stdio.h>
#include<string.h>
#include<queue>
#define N 210
using namespace std;
int map[N][N],color[N],vis[N],match[N],n,m;
int find(int x)
{
for(int i=1;i<=n;i++)
{
if(vis[i]==0&&map[x][i]==1)
{
vis[i]=1;
if(match[i]==-1||find(match[i])==1)......
阅读全文