UVA-4288 Cat vs. Dog （最大独立集）

题目大意：猫狗大赛，s个猫和t个狗，有v个投票者，他们不是爱猫者就是爱狗者，所以爱猫者一定会对某条猫投晋级票，对某条狗投淘汰票，爱狗者亦然。现在已知这v个人的投票情况，应该使哪些畜牲晋级或淘汰才能使投票者满意（喜欢的晋级，讨厌的淘汰）的人数最多？求出最多满意人数。

题目分析：有同一爱好的人群之间不会有矛盾。当爱猫者的晋级票与爱狗者的淘汰票是同一只猫或爱猫者的淘汰票与爱狗者的晋级票是同一条狗时，视为这二人有矛盾，在他们之间连一条有向边，把所有有矛盾的人找出来建一张有向图。这就意味着一条边的两端点的投票方案至少有一个不被采纳，这就变成了最大独立集问题。

代码如下：

# include<iostream>
# include<cstdio>
# include<string>
# include<vector>
# include<cstring>
# include<algorithm>
using namespace std;
# define REP(i,s,n) for(int i=s;i<n;++i)
# define CL(a,b) memset(a,b,sizeof(a))
# define CLL(a,b,n) fill(a,a+n,b)

const int N=505;
struct voter
{
    int a,b;
    voter(){}
    voter(int _a,int _b):a(_a),b(_b){}
};
voter v1[N],v2[N];
int n,m,w[N][N],vis[N],link[N];

bool dfs(int x)
{
    REP(y,0,m){
        if(!w[x][y]||vis[y]) continue;
        vis[y]=1;
        if(link[y]==-1||dfs(link[y])){
            link[y]=x;
            return true;
        }
    }
    return false;
}

int match()
{
    int res=0;
    CL(link,-1);
    REP(i,0,n){
        CL(vis,0);
        if(dfs(i)) ++res;
    }
    return res;
}

int main()
{
    int T,vote;
    string p,q;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&vote);
        n=m=0;
        while(vote--)
        {
            cin>>p>>q;
            int a=0;
            REP(i,1,p.size()) a=a*10+p[i]-'0';
            int b=0;
            REP(i,1,q.size()) b=b*10+q[i]-'0';
            if(p[0]=='C'&&q[0]=='D') v1[n++]=voter(a,b);
            if(p[0]=='D'&&q[0]=='C') v2[m++]=voter(a,b);
        }
        CL(w,0);
        REP(i,0,n) REP(j,0,m) if(v1[i].a==v2[j].b||v1[i].b==v2[j].a) w[i][j]=1;
        printf("%d
",n+m-match());
    }
    return 0;
}

UVA-4288 Cat vs. Dog （最大独立集）

相关推荐