题目链接：
hihocoder1122
代码:
#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<queue>#define maxn 1550using namespace std;vector<int>to[maxn];int vis[maxn]; int link[maxn];int vis2[maxn];int n;void bfs()//染色 有0和1两种颜色表示两种性别{queue<int>q;int head,next;for(int j=1; j<=n; j++){if(vis[j]!=-1)continue;vis[j]=1;q.push(j);while(!q.empty()){head=q.front();q.pop();for(int i=0; i<to[head].size(); i++){next=to[head][i];if(vis[next]==-1){vis[next]=!vis[head];q.push(next);}}}}return;}int can(int x){for(int i=0; i<to[x].size(); i++){int next=to[x][i];if(!vis2[next]){vis2[next]=1;if(!link[next]||can(link[next])){link[next]=x;return 1;}}}return 0;}int main(){freopen("in.txt","r",stdin);int m,a,b;memset(vis,-1,sizeof(vis));memset(link,0,sizeof(link));scanf("%d%d",&n,&m);while(m–){scanf("%d%d",&a,&b);to[a].push_back(b);to[b].push_back(a);}bfs();int ans=0;for(int i=1; i<=n; i++) //匈牙利算法{memset(vis2,0,sizeof(vis2));if(vis[i]==1&&can(i))ans++;}cout<<ans<<endl;return 0;}
其实可以不用将图染色的
可以直接用匈牙利算法枚举所有点 得到的最大匹配数/2即为答案
，今天不想走，明天就要跑了。
