首页 > 代码库 > HDU 1068

HDU 1068

2024-07-22 08:02:44   220人阅读

【原题】

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

【类型】

二分图最大独立集（最大二分匹配）

【题意】

题目给定一些男女生之间相互的romantic关系，要求找出一个最大的集合，使得该集合中的所有男女生之间都不存在romantic关系。

【分析】

一个二分图的最大独立集点数与最大二分匹配个数有直接的关系：

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

故本题直接转化为求最大二分匹配即可，需要注意的是，题中给出的条件是1指向2，2也会指向1，所以最终算出来的匹配数其实是实际对数的两倍，最终被顶点数减去之前首先需要折半。

基础二分匹配练手题。

 1 /* 2 ID:   Chen Fan 3 PROG: hdu1068 4 LANG: G++ 5 */ 6  7 #include<iostream> 8 #include<cstdio> 9 #include<cstring>10 #include<algorithm>11 12 using namespace std;13 14 typedef struct nod15 {16     17     int a,b;18 } node;19 node a[1000];20 int result[1000],start[1000],num[1000];21 bool flag[1000];22 23 bool op(node a,node b)24 {25     if (a.a==b.a) return a.b<b.b;26     else return a.a<b.a;27 }28 29 bool find(int s)30 {31     for (int i=0;i<num[s];i++)32     {33         int now=a[start[s]+i].b;34         if (!flag[now])35         {36             flag[now]=true;37             if (result[now]==-1||find(result[now]))38             {39                 result[now]=s;40                 return true;41             }42         }43     }44     return false;45 }46     47 int main()48 {49     int n;50     while (scanf("%d",&n)!=EOF)51     {52         int tail=0;53         for (int i=1;i<=n;i++)54         {55             int x,p;56             scanf("%d: (%d",&x,&p);57             getchar();58             for (int j=1;j<=p;j++)59             {60                 int y;61                 scanf("%d",&y);62                 tail++;63                 a[tail].a=x;64                 a[tail].b=y;65             }66         }67         sort(&a[1],&a[tail+1],op);68         int o=-1;69         memset(num,0,sizeof(num));70         for (int i=1;i<=tail;i++)71         {72             if (o!=a[i].a)73             {74                 o=a[i].a;75                 start[o]=i;76             }77             num[o]++;78         }79         80         memset(result,-1,sizeof(result));81         int ans=0;82         for (int i=0;i<n;i++)83         {84             memset(flag,0,sizeof(flag));85             if (find(i)) ans++;86         }87         88         printf("%d\n",n-ans/2);89     }90     91     return 0;92 }
View Code

 

HDU 1068


联系
我们