HDU - 2444 The Accomodation of Students(二分图判断+二分图最大匹配)

题目链接：点击查看

题目大意：给出n个学生，他们之间有m个认识关系，但认识关系不具有传递性，比如A认识B，B认识C，A不一定认识C，现在给出认识关系，先判断是否能够将所有学生分为两个集合A和B中去，集合A中的所有学生都互不认识，集合B中的学生也互不认识，集合A中的学生可以和集合B中的学生认识，若能分成两个集合，问最多有几个认识的关系

题目分析：看完题后再看了一眼样例，就是个模板题，二分图的判断我们交叉染色即可判断，分成两个集合后用匈牙利跑一下最大匹配就行了

代码：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=210;vector<int>node[N];int n,m;bool maze[N][N];int match[N];bool vis[N];int color[N];bool dfs1(int u,int f,int c)//交叉染色法 {color[u]=c;for(auto v:node[u]){if(v==f)continue;if(color[v]==-1&&!dfs1(v,u,!c))return false;else if(color[v]!=-1&&color[v]==c)return false;}return true; }bool dfs(int x)//匈牙利算法 {for(int i=1;i<=n;i++){if(maze[x][i]&&!vis[i]){vis[i]=true;if(!match[i]||dfs(match[i])){match[i]=x;return true;}}}return false; }void init() {for(int i=1;i<=n;i++)node[i].clear();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)maze[i][j]=false;memset(match,0,sizeof(match));memset(color,-1,sizeof(color)); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d",&n,&m)!=EOF){init();while(m--){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);maze[u][v]=true;}if(!dfs1(1,0,0)){printf("No\n");continue;}int ans=0;for(int i=1;i<=n;i++){memset(vis,false,sizeof(vis));if(dfs(i))ans++;}printf("%d\n",ans);}return 0; }

 

总结

以上是生活随笔为你收集整理的HDU - 2444 The Accomodation of Students(二分图判断+二分图最大匹配)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。