HDU 2444 The Accomodation of Students 二分图匹配
题目来源：
题意：
给出学生数n和关系数m，接下来给出m个关系。
要求将学生分成两部分，每一部分不能有互相认识的人。做不到就输出"No"。
若上一步满足，则将学生配对，要求这两个学生互相认识。
题解：
一个难点是建图，要求只是满足每一部分不能有认识的就好。
建完图直接二分图最大匹配输出结果就好。
代码：
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int n,m;
const int maxn=200+10;
vector<pair<int,int> >mp;
int G[maxn][maxn];
int matched[maxn];
int vi[maxn];
int l[maxn],r[maxn];
int dfs(int x)
{
for(int i=0;i<maxn;i++)
{
if(G[x][i] && !vi[i])
{
vi[i]=1;
if(matched[i]==-1||dfs(matched[i]))
{
matched[x]=i;
matched[i]=x;
return 1;
}
}
}
return 0;
}
int solve()
{
int ans=0;
memset(matched,-1,sizeof(matched));
for(int i=0;i<maxn;i++)
{
memset(vi,0,sizeof(vi));
ans+=dfs(i);
}
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
//freopen("3.in","r",stdin);
//freopen("3.out","w",stdout);
#endif
int a,b;
bool flag;
while(cin >> n >> m)
{
flag=false;
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
mp.clear();
memset(G,0,sizeof(G));
for(int i=0;i<m;i++)
{
cin >> a>> b;
mp.push_back(make_pair(a,b));
}
for(int i=0;i<m;i++)
{
if((l[mp[i].first] && l[mp[i].second])||(r[mp[i].first]&& r[mp[i].second]))
{
flag=1;
break;
}
l[mp[i].first]=1;
r[mp[i].second]=1;
G[mp[i].first][mp[i].second]=1;
}
if(flag)
cout <<"No"<<endl;
else
{
cout <<solve()<<endl;
}
}
return 0;
}