发布于 由itewqq

[二分图][建图] UVa 12168 Cat vs Dog

比赛时候其实想的就是正解，但是没时间实现了。

这里并不是把猫狗分离开来，而是把voter分离开，换句话说原来的边变成了点，支持猫的在一边，支持狗的在另一边，如果有冲突的话连一条边，这样的话就是求最大独立集了。

本来看这个输入感觉头疼，后来想了想，忽然意识到：1 重复的人可以不用管，照例读入建立点，因为把他变成点之后对图没有任何影响。2  可以不用管字符后的数字，直接把他们当成一个整体就好了，整个字符串比较。 3  建立图的时候可以不用分左右两边，只要i和j有冲突就line[i][j]=line[j][i]=1；这样会使得建图的过程更简单，然后相当于把二分图对称了一下，最后输出的时候最大匹配数除以2就可以了.

//#include 
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=10000+5;
const int mod=1e9+7;
int ct,dt,vt;
bool line[505][505],used[505];
int link[505],cnt[505];
bool found(int x)
{
    for (int i=1;i<=vt;i++)
    {
        if(line[x][i]&&!used[i])
        {
            used[i]=1;
            if(!link[i]||found(link[i]))
            {
                link[i]=x;
                return 1;
            }
        }
    }
    return 0;
}

pair  ns[505];

int main()
{
    int T,ans;
    string a,b;
    scanf("%d",&T);
    while(T--)
    {
        ans=0;
        memset(line,0,sizeof(line));
        memset(link,0,sizeof(link));
        scanf("%d%d%d",&ct,&dt,&vt);
        for (int i=1;i<=vt;i++)
            cin>>ns[i].first>>ns[i].second;
        for (int i=1;i<=vt;i++)
            for (int j=i+1;j<=vt;j++)
            if(ns[i].first==ns[j].second||ns[j].first==ns[i].second)
                line[i][j]=line[j][i]=1;
        for (int i=1;i<=vt;i++)
        {
            memset(used,0,sizeof(used));
            if(found(i))ans++;
        }
        printf("%d\n",vt-ans/2);
    }
    return 0;
}

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。