欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Divide Groups HDU - 4751(二分图染色)

程序员文章站 2022-05-22 14:04:41
...

Divide Groups HDU - 4751

题意:

有n个人,第 i i i 个人认识一些人(可能互相认识)
现在要你设计两场活动,使尽可能多的人互相认识

思路:

  1. 显然是二分图染色。
  2. 本题有一个条件,就是已经认识的,就无关紧要了

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;
}

相关标签: # 二分图