<span>HDU2444 二分图判断+最大匹配</span>
题意：
给你n个点m条边的图，判断是否为二分图
如果不是输出No
如果是输出最大匹配
判断用交叉染色法（dfs简单bfs防暴）
最大匹配跑一边匈牙利算法
/* *********************************************** Author :devil Created Time :2016/5/6 16:6:31 ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; const int N=205; int n,m,x,y,col[N],link[N]; bool vis[N]; vector<int>eg[N]; int dfs(int u) { for(int i=0; i<eg[u].size(); i++) { int v=eg[u][i]; if(!vis[v]) { vis[v]=1; if(link[v]==-1||dfs(link[v])) { link[v]=u; return 1; } } } return 0; } //bool color(int u) //{ // for(int i=0;i<eg[u].size();i++) // { // int v=eg[u][i]; // if(!col[v]) // { // col[v]=!col[u]; // if(!color(v)) return 0; // } // else if(col[v]==col[u]) return 0; // } // return 1; //} bool color(int u) { queue<int>q; q.push(u); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0;i<eg[u].size();i++) { int v=eg[u][i]; if(!col[v]) { col[v]=!col[u]; q.push(v); } else if(col[v]==col[u]) return 0; } } return 1; } int main() { //freopen("in.txt","r",stdin); while(~scanf("%d%d",&n,&m)) { for(int i=1; i<=n; i++) eg[i].clear(); memset(link,-1,sizeof(link)); memset(col,0,sizeof(col)); while(m--) { scanf("%d%d",&x,&y); eg[x].push_back(y); eg[y].push_back(x); } col[1]=1; if(!color(1)) { printf("No\n"); continue; } int ans=0; for(int i=1; i<=n; i++) { memset(vis,0,sizeof(vis)); ans+=dfs(i); } printf("%d\n",ans/2); } return 0; }
