Divide Groups HDU - 4751(二分图染色)
程序员文章站
2022-05-22 14:04:41
...
Divide Groups HDU - 4751
题意:
有n个人,第
i
i
i 个人认识一些人(可能互相认识)
现在要你设计两场活动,使尽可能多的人互相认识
思路:
- 显然是二分图染色。
- 本题有一个条件,就是已经认识的,就无关紧要了
AC
#include <iostream>
#include <vector>
#include <cstring>
#define pb push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define For(i,x,y) for(int i=(x); i<=(y); i++)
using namespace std;
const int maxn=100+10;
vector<int>e[maxn];
int g[maxn][maxn];
int color[maxn],n;
int fl=0;
void ans(int a){
if(a)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
bool dfs(int u){
For(v,1,n){//for(int i=0; i<e[u].size(); i++){
//int v=e[u][i];
if(v==u||g[u][v]&&g[v][u])continue;
if(color[u]==color[v])return false;
if(!color[v]){
color[v]=3-color[u];
if(!dfs(v))return false;
}
}
return true;
}
int main()
{
ios::sync_with_stdio(0);
while(cin>>n){
mst(g,0);
mst(color,0);fl=1;
int v;
For(u,1,n){
//e[u].clear();
while(cin>>v,v)g[u][v]=1;//e[u].pb(v);
}
For(i,1,n){
if(!color[i]){
color[i]=1;
if(dfs(i))continue;
fl=0;
break;
}
}
ans(fl);
}
return 0;
}
上一篇: Ubuntu 10.10下Qt连接MySQL数据库
下一篇: 吃“软饭”的兄弟,你们过得好吗?
推荐阅读