HDU--3829--Cat VS Dog【最大点独立集】-白红宇

HDU--3829--Cat VS Dog【最大点独立集】

阅读量：7035 次

发布时间：2019-06-28

本文共 1995 字，大约阅读时间需要 6 分钟。

链接：

题意：动物园有n条狗，m头猫，p个小孩。每一个小孩有一个喜欢的动物和讨厌的动物，如今动物园要转移一些动物，假设一个小孩喜欢的动物在，不喜欢的动物不在，他就会happy，问动物最多能使几个小孩happy。

思路：一个比較明显的二分图。不能以猫狗为顶点，那样找到的是哪些动物会转移，以小孩为顶点，找出最大点独立集，有两种建图方式。一种是以小孩总数p为左右点集的顶点个数。假设小孩a喜欢的动物是小孩b不喜欢的动物。就连一条边edge(a,b)；另外一种是以喜欢猫的小孩总数为左顶点个数，喜欢狗的为右顶点，依据矛盾连边。

这样两种仅仅是顶点数目不同。

然后找二分图最大点独立集

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

只是第一种建图左右顶点数都是p，也就是每一个小孩在左右都有出现。总共出现两次，所以找到最大点独立集后除以2就是答案。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      using namespace std;#define PI acos(-1.0)#define MAXN 500010#define eps 1e-7#define INF 0x3F3F3F3F //0x7FFFFFFF#define LLINF 0x7FFFFFFFFFFFFFFF#define seed 1313131#define MOD 1000000007#define ll long long#define ull unsigned ll#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1struct node{ int v,next;}edge[MAXN];int head[510],vis[510],dx[510],dy[510];int cnt,n1,n2; //n1左边的点数，n2右边的点数void add_edge(int a,int b){ edge[cnt].v = b; edge[cnt].next = head[a]; head[a] = cnt++;}int path(int u){ int i, j; for(i=head[u];i!=-1;i=edge[i].next){ int v = edge[i].v; if(!vis[v]){ vis[v] = 1; if(dy[v] == -1 || path(dy[v])){ dx[u] = v; dy[v] = u; return 1; } } } return 0;}int maxmatch(){ int i, j; int res = 0; memset(dx,-1,sizeof(dx)); memset(dy,-1,sizeof(dy)); for(i=1;i<=n1;i++){ if(dx[i]==-1){ memset(vis,0,sizeof(vis)); res += path(i); } } return res;}struct Node{ string like,dislike;}animal[505];int main(){ int n,m,p,i,j; while(scanf("%d%d%d",&n,&m,&p)!=EOF){ cnt = 0; memset(head,-1,sizeof(head)); for(i = 0; i < p; i++){ cin>>animal[i].like>>animal[i].dislike; } n1 = p; for(i = 0; i < p; i++){ for(j = 0; j < p; j++){ if(animal[i].like == animal[j].dislike || animal[i].dislike == animal[j].like){ add_edge(i + 1, j + 1); } } } int ans = maxmatch(); printf("%d\n", (2 * p - ans) / 2); } return 0;}

转载于:https://www.cnblogs.com/yutingliuyl/p/6883326.html

你可能感兴趣的文章

java中文乱码解决之道（六）—–javaWeb中的编码解码