表单大师 做网站,前端做图表的网站,四川住房和城乡建设厅网站电话,找小网站的关键词HDU 2444 The Accomodation of Students 二分图匹配 题目来源#xff1a; HDU题意#xff1a; 给出学生数n和关系数m#xff0c;接下来给出m个关系。 要求将学生分成两部分#xff0c;每一部分不能有互相认识的人。做不到就输出No。 若上一步满足#xff0c;则…HDU 2444 The Accomodation of Students 二分图匹配 题目来源 HDU题意 给出学生数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 maxn20010;
vectorpairint,int mp;
int G[maxn][maxn];
int matched[maxn];
int vi[maxn];
int l[maxn],r[maxn];int dfs(int x)
{for(int i0;imaxn;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 ans0;memset(matched,-1,sizeof(matched));for(int i0;imaxn;i){memset(vi,0,sizeof(vi));ansdfs(i);}return ans;
}int main()
{
#ifndef ONLINE_JUDGE//freopen(3.in,r,stdin);//freopen(3.out,w,stdout);
#endifint a,b;bool flag;while(cin n m){flagfalse;memset(l,0,sizeof(l));memset(r,0,sizeof(r));mp.clear();memset(G,0,sizeof(G));for(int i0;im;i){cin a b;mp.push_back(make_pair(a,b));}for(int i0;im;i){if((l[mp[i].first] l[mp[i].second])||(r[mp[i].first] r[mp[i].second])){flag1;break;}l[mp[i].first]1;r[mp[i].second]1;G[mp[i].first][mp[i].second]1;}if(flag)cout Noendl;else{cout solve()endl;}}return 0;
}转载于:https://www.cnblogs.com/Combustible-ice/p/5894042.html
