首页 > 代码库 > HDU 3829

HDU 3829

2024-07-08 22:28:28   222人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=2970

P个小朋友喜欢猫讨厌狗，喜欢狗讨厌猫，移除一定数量的猫狗，使开心的小朋友数量最多

二分图最大独立集=顶点数-二分图最大匹配

对喜好冲突的小朋友连边，因为对小朋友建图拆了点，求出的最大匹配要除以2

和hdu 1068是一个意思

二分图最大独立集和最大匹配的含义在题目中是相反的，比如这道题要求开心的小朋友的最大独立集，二分图建图的时候就要用不开心的小朋友组合连边，这类题目一定是给出冲突的关系，才可以去求解

#include <iostream>#include <cstdio>#include <cstring>using namespace std ;int T,M[505][505],n,m,linkx[505],linky[505],vis[505] ;int find(int s){    for(int i=1 ;i<=m ;i++)    {        if(M[s][i])        {            if(vis[i]==T)continue ;            vis[i]=T ;            if(!linky[i] || find(linky[i]))            {                linky[i]=s ;                linkx[s]=i ;                return 1 ;            }        }    }    return 0 ;}int max_match(){    int ans=0 ;    memset(linkx,0,sizeof(linkx)) ;    memset(linky,0,sizeof(linky)) ;    memset(vis,0,sizeof(vis)) ;    for(int i=1 ;i<=n ;i++)    {        T=i ;        ans+=find(i);    }    return ans;}char like[505][15],dislike[505][15] ;int main(){    int nn,mm,P ;    while(~scanf("%d%d%d",&nn,&mm,&P))    {        n=m=P ;        for(int i=1 ;i<=n ;i++)        {            scanf("%s%s",like[i],dislike[i]) ;        }        memset(M,0,sizeof(M)) ;        for(int i=1 ;i<=n ;i++)        {            for(int j=1 ;j<=n ;j++)            {                if(!strcmp(like[i],dislike[j]) || !strcmp(like[j],dislike[i]))                {                    M[i][j]=1 ;                }            }        }        printf("%d\n",P-max_match()/2) ;    }    return 0 ;}
View Code

 


联系
我们