题解 UVA12083 【Guardian of Decency】

数学系 · 2018-06-28 10:12:01 · 题解

这题明显是求二分图的最大独立集。
而最大独立集和最小覆盖集是互补的。
最小覆盖，就是求二分图最大匹配。
将所有可能在一起的人用无向边连起来，求二分图最大匹配，
答案就是总人数减去最大匹配数。

//思路：先将所有不满足条件的人按性别建立二分图，再求二分图的最大独立级即二分图节点数减去二分图最小覆盖集（二分图最大匹配）。 
//在洛谷和poj上提交时，数据量不同，需更改maxn和maxm的值。 
//本代码可在洛谷AC，用时310ms 
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>

using namespace std;

const int MAXN=100001;
const int MAXM=201;

struct node
{
    int v;
    node *next;
}pool[MAXN<<1],*G[MAXN];
int cnt=0;

struct STUDENT
{
    int height;
    char gender;
    char musics[MAXM];
    char sports[MAXM];
}student[MAXN]; 

int num=0;

void addedge(int u,int v)
{
    node *p=&pool[++cnt];
    node *q=&pool[++cnt];
    p->v=v;p->next=G[u];G[u]=p;
    q->v=u;q->next=G[v];G[v]=q;
}

int match[MAXN];
bool vis[MAXN];
int ans;

int dfs(int p)
{
    for(node *v=G[p];v;v=v->next)
    {
        if(!vis[v->v])
        {
            vis[v->v]=true;
            if(!match[v->v])
            {
                match[p]=v->v;
                match[v->v]=p;
                return 1;
            }
            else if(dfs(match[v->v]))
            {
                match[p]=v->v;
                match[v->v]=p;
                return 1;
            }
        }
    }
    return 0;
}

bool sports_and_musics(int a,int b)
{
    bool music=true;
    bool sport=true;
    for(int i=0;i<MAXM;i++)
    {
        if(student[a].musics[i]!=student[b].musics[i])
            music=false;
        if(student[a].sports[i]!=student[b].sports[i])
            sport=false;
    }
    return music&&(!sport);
}

int main()
{
    int t;
    string tmp;
    cin>>t;
    int cp=0;
    while(t--)
    {
        memset(pool,0,sizeof(pool));
        memset(G,0,sizeof(G));
        cnt=0;
        memset(student,0,sizeof(student));
        memset(match,0,sizeof(match));
        num=0;
        ans=0;
        cin>>num;
        for(int i=1;i<=num;i++)
        {
            cin>>student[i].height;
            cin>>student[i].gender;
            cin>>student[i].musics;
            cin>>student[i].sports;

            for(int j=1;j<i;j++)
            {
                if((-40<=student[i].height-student[j].height && student[i].height-student[j].height<=40) && student[i].gender!=student[j].gender && sports_and_musics(i,j))
                {
                    addedge(i,j);
                }
            }
        }
        for(int i=1;i<=num;i++)
        {
            if(!match[i])
            {
                memset(vis,0,sizeof(vis));
                ans+=dfs(i);
            }
        }
        cout<<num-ans<<endl;
    }
    return 0;
}