POJ3692 最大点权独立集元素个数

题意：

n个男孩和m个女孩，给你他们谁和谁彼此了解，问你要找到一个集合，使得这个集合中的男孩和女孩相互了解，并且人数最多。

思路：

简单题目，其实就是在求最大点权独立集元素个数，先说下点券独立集的概念，就是给你一些关系，让你找到一个最大的集合，使得集合中的任意两个人之间都不会有关系，用的是匈牙利算法，对于这个题目我们可以吧不了解的连接到一起，这样得到的就是集合中任意两人都了解的最大人数了，最大点券独立集元素个数 = n + m - 最大匹配数。

#include<stdio.h>

#include<string.h>

#define N_node 200 + 10

#define N_edge 40000 + 20

typedef struct

{

   int to ,next;

}STAR;

STAR E[N_edge];

int list[N_node] ,tot;

int map[N_node][N_node];

int mk_dfs[N_node] ,mk_gx[N_node];

void add(int a ,int b)

{

   E[++tot].to = b;

   E[tot].next = list[a];

   list[a] = tot;

}

int DFS_XYL(int s)

{

   for(int k = list[s] ;k ;k = E[k].next)

   {

       int to = E[k].to;

       if(mk_dfs[to]) continue;

       mk_dfs[to] = 1;

       if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to]))

       {

           mk_gx[to] = s;

           return 1;

       }

   }

   return 0;

}

int main ()

{

   int n ,m ,k ,i ,j;

   int a ,b ,cas = 1;

   while(~scanf("%d %d %d" ,&n ,&m ,&k) && n + m + k)

   {

      memset(map ,0 ,sizeof(map));

      for(i = 1 ;i <= k ;i ++)

      {

         scanf("%d %d" ,&a ,&b);

         map[a][b] = 1;

      }

      memset(list ,0 ,sizeof(list));

      tot = 1;

      for(i = 1 ;i <= n ;i ++)

      for(j = 1 ;j <= m ;j ++)

      if(!map[i][j]) add(i ,j);

      memset(mk_gx ,255 ,sizeof(mk_gx));

      int sum = 0;

      for(i = 1 ;i <= n ;i ++)

      {

         memset(mk_dfs ,0 ,sizeof(mk_dfs));

         sum += DFS_XYL(i);

      }

      printf("Case %d: %d\n" ,cas ++ ,m + n - sum);

   }

   return 0;

}

巴特西

POJ3692 最大点权独立集元素个数

最新文章

热门文章