HDU 2444 The Accomodation of Students 二分圖匹配

題目來(lái)源：

• HDU

題意：

給出學(xué)生數(shù)n和關(guān)系數(shù)m，接下來(lái)給出m個(gè)關(guān)系。
要求將學(xué)生分成兩部分，每一部分不能有互相認(rèn)識(shí)的人。做不到就輸出"No"。
若上一步滿足，則將學(xué)生配對(duì)，要求這兩個(gè)學(xué)生互相認(rèn)識(shí)。

題解：

一個(gè)難點(diǎn)是建圖，要求只是滿足每一部分不能有認(rèn)識(shí)的就好。
建完圖直接二分圖最大匹配輸出結(jié)果就好。

代碼：

#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); #endifint 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; }

轉(zhuǎn)載于:https://www.cnblogs.com/Combustible-ice/p/5894042.html

總結(jié)

以上是生活随笔為你收集整理的HDU 2444 The Accomodation of Students 二分图匹配的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。