【题目链接】：click here~~
【题目大意】：
给出N个人和M对关系，表示a和b认识，把N个人分成两组，同组间任意俩人互不认识，若不能分成两组输出No，否则输出两组间俩人互相认识的对数
【解题思路】: 先判断能否构成二分图，判断二分图用交叉染色法：从某个未染色的点出发把此点染成白色，该点周围的点染成黑色，黑色周围的又染成白色，若走到某个点已经染色，并且它相邻点的颜色与它一样则不是二分图，可以这样理解，染白色既加入X集合，黑色既加入Y集合，若某个点即是X集合又是Y集合，那说明不是二分图，判断二分图之后，再求最大的匹配数，PS：二分图是无向图时最大匹配数是Sum/2。
代码：
#pragma comment(linker, "/STACK:1024000000,1024000000")#include <cctype>#include <cerrno>#include <cfloat>#include <ciso646>#include <climits>#include <clocale>#include <cmath>#include <csetjmp>#include <csignal>#include <cstdarg>#include <cstddef>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>// C++#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <exception>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iosfwd>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <locale>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <set>#include <sstream>#include <stack>#include <stdexcept>#include <streambuf>#include <string>#include <typeinfo>#include <utility>#include <valarray>#include <vector>#define rep(i,j,k) for(int i=(int)j;i<(int)k;++i)#define per(i,j,k) for(int i=(int)j;i>(int)k;–i)#define lowbit(a) a&-a#define Max(a,b) a>b?a:b#define Min(a,b) a>b?b:a#define mem(a,b) memset(a,b,sizeof(a))int dir4[4][2]= {{1,0},{0,1},{-1,0},{0,-1}};int dir8[8][2]= {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};int movv[5][2]= {{1,0},{0,1},{0,0},{-1,0},{0,-1}};using namespace std;typedef long long LL;typedef unsigned long long LLU;typedef double db;const int inf=0x3f3f3f3f;const int N =205;int head[N],link[N];///邻接表bool vis[N],col[N];int cnt,n,m;inline LL read(){int c=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}return c*f;}struct edge{int to;int next;}g[N*N];void init(){cnt=0;mem(head,-1);mem(col,0);}void add_edge(int u,int v){g[cnt].to=v;g[cnt].next=head[u];head[u]=cnt++;}bool color(int u){ ///染色 for(int i=head[u]; i!=-1; i=g[i].next){int v = g[i].to;if(!col[v]){col[v] = !col[u];if(!color(v)) return false;}else if(col[v]==col[u]) return false; } return true;}bool dfs(int u) ///匈牙利算法dfs实现{for(int i=head[u]; i!=-1; i=g[i].next){///元素集合个数int v=g[i].to;if(!vis[v]){vis[v]=1;if(link[v]== -1|| dfs(link[v])){link[v]=u;return true;}}}return false;}int match() ///最大匹配{int ans = 0;mem(link,-1);for(int i=1; i<=n; ++i){mem(vis,0);if(dfs(i)) ans++;}return ans;}int main(){while(~scanf("%d%d",&n,&m)){if(n==1){puts("No");continue;}init();while(m–){int u,v;u=read(),v=read();add_edge(u,v);add_edge(v,u);}col[1]=1;if(!color(1)) puts("No");else printf("%d\n",match()>>1);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，每天告诉自己我很棒!
