题解 UVA12083 【Guardian of Decency】

· · 题解

二分图最大匹配

这道题最大的难度在于预处理出无向图

前排兜售小广告

题目翻译：

Frank N. Stein是一位非常保守的高中老师。他想带一些学生参加
游览，但他担心他们中的一些人可能成为夫妻。虽然你永远不能排除这一点
可能性，他已经制定了一些规则，他认为这表明两个人的概率很低
一对夫妇：
•它们的高度相差超过40厘米。
•他们属于同一性别。
•他们喜欢的音乐风格不同。
•他们最喜欢的运动是相同的（他们很可能是不同球队的球迷，那会是
导致战斗）。
因此，对于他带来短途旅行的任何两个人，他们必须至少满足其中一个
以上要求。鉴于他们至关重要，帮助他找到他可以承受的最多人数
信息。
输入
输入的第一行包含一个整数T≤100，给出了测试用例的数量。第一行
每个测试用例包含一个N≤500的整数，给出学生的数量。接下来会有一个
每个学生的行由四个以空格分隔的数据项组成：
•整数h，以cm为单位给出高度;
•女性角色'F'或男性角色'M';
•描述首选音乐风格的字符串;
•带有喜爱运动名称的字符串。
输入中的字符串不会包含超过100个字符，任何字符串也不会包含任何字符串
空白。

这里预处理时使用string里的compare

compare使用示例：

std::string str1 ("green apple");
  std::string str2 ("red apple");

  if (str1.compare(str2) != 0)
    std::cout << str1 << " is not " << str2 << '\n';

  if (str1.compare(6,5,"apple") == 0)//第一个参数表示str1中的位置:str1[6],第二个参数表示要比较的字符串的最大数量,即从指定位置开始后的比较数目
    std::cout << "still, " << str1 << " is an apple\n";

  if (str2.compare(str2.size()-5,5,"apple") == 0)//同上
    std::cout << "and " << str2 << " is also an apple\n";

  if (str1.compare(6,5,str2,4,5) == 0)//str1中的“apple”和str2中的“apple”比较
    std::cout << "therefore, both are apples\n"

预处理完 跑一个最大匹配即可 （不会右转二分图匹配）

ac代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100001;
struct node//链式前向星
{
    int v;
    int next;
}G[MAXN];
int head[MAXN];
int cnt;
struct stu
{
    int h;
    char sex;
    string musics;
    string sports;
    stu(){sports = musics = "12213124142";}

}stu[MAXN]; 
int num=0;
void add(int u,int v)//加边
{
    G[++cnt].v=v;
    G[cnt].next=head[u]; 
    head[u]=cnt;
}
int result[MAXN];
bool vis[MAXN];
int ans;
int find(int p)//最大匹配
{
    for(int i=head[p];i;i=G[i].next)
    {
        int to=G[i].v;;
        if(!vis[to])
        {
            vis[to]=true;
            if(!result[to])
            {
                result[p]=to;
                result[to]=p;
                return 1;
            }
            else if(find(result[to]))
            {
                result[p]=to;
                result[to]=p;
                return 1;
            }
        }
    }
    return 0;
}
bool music(int i,int j)
{
    int ans=stu[i].musics.compare(1,stu[i].musics.length(),stu[j].musics,1,stu[j].musics.length());
    if(ans==0) return true;
    else return false;
}
bool sports(int i,int j)
{
    int ans=stu[i].sports.compare(1,stu[i].sports.length(),stu[j].sports,1,stu[j].sports.length());
    if(ans==0) return false;
    else return true;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(G,0,sizeof(G));
        memset(head,0,sizeof(head));
        cnt=0;
        memset(result,0,sizeof(result));
        num=0;
        ans=0;
        cin>>num;
        for(int i=1;i<=num;i++)
        {
            cin>>stu[i].h;
            cin>>stu[i].sex;
            cin>>stu[i].musics;
            cin>>stu[i].sports;
            for(int j=1;j<i;j++)
            {
                if((-40<=stu[i].h-stu[j].h && stu[i].h-stu[j].h<=40) && stu[i].sex!=stu[j].sex && sports(i,j)&&music(i,j))
                {
                    add(i,j);
                    add(j,i);
                }
            }
        }
        for(int i=1;i<=num;i++)
        {
            if(!result[i])
            {
                memset(vis,0,sizeof(vis));
                ans+=find(i);
            }
        }
        cout<<num-ans<<endl;        
        for(int i=1;i<=num;i++)//不要忘记清零
        {
            stu[i].sex=' ';
            stu[i].h=0;
            stu[i].musics.clear();  
            stu[i].sports.clear();  
        }
    }
    return 0;
}