博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Gym-101915D Largest Group 最大独立集 Or 状态压缩DP
阅读量:5822 次
发布时间:2019-06-18

本文共 1622 字,大约阅读时间需要 5 分钟。

题意:给你N个男生,N个女生,男生与男生之间都是朋友,女生之间也是,再给你m个关系,告诉你哪些男女是朋友,最后问你最多选几个人出来,大家互相是朋友. N最多为20

题解:很显然就像二分图了,男生一边女生一边的,然后一种解法就是

        求图的最大独立集,(看起来很巧,实则也不知道为何2333)

        (最大独立集是一个点集,其中任意两点在图中无对应边,对于一般图来说,最大独立集是一个NP完全问题,对于二分图来说最大独立集=|V|-二分图的最大匹配数)

        我们本来连边是,所有的朋友关系连边(男女就行了,同性都可以忽略了因为肯定可以)

       但我们现在把这个图边连满,然后把有关系的边删掉,再求最大独立集,此时要求他们没有对应边不就是实际上选了那条边了吗

     

1 #include
2 #define N 155 3 int T,n,m,x,y,used[N],g[N][N],val[N],ans; 4 using namespace std; 5 int dfs(int x) 6 { 7 for (int i=1;i<=n;i++) 8 { 9 if (g[x][i]==-1) continue;10 if (!used[i])11 {12 used[i]=1;13 if (val[i]==-1 || dfs(val[i]))14 {15 val[i]=x;16 return 1;17 }18 }19 }20 return 0;21 }22 int main() 23 {24 scanf("%d",&T);25 while(T--) 26 {27 scanf("%d%d",&n,&m);28 memset(g,0,sizeof(g));29 memset(val,-1,sizeof(val));30 while (m--)31 {32 scanf("%d%d",&x,&y);33 g[x][y]=-1; 34 } 35 ans=2*n;36 for (int i=1;i<=n;i++)37 {38 memset(used,0,sizeof(used));39 ans-=dfs(i); 40 }41 printf("%d\n",ans);42 }43 }

 

 

         赛后,其他队有人写的是状态压缩dp,哈哈,一看数据范围20,确实可以直接暴力统计答案了,

         f[st]表示男生状态为st的时候,女生的状态为什么(st是一个20位的数,f[st]也是哈,每位0,1表示这个人选不选)

         题解直接就写在下面代码注释了

       

1 #include
2 using namespace std; 3 #define lld long long 4 int T,n,m,f[1<<20+1],x,y,ll[50]; 5 int main() 6 { 7 scanf("%d",&T); 8 while (T--) 9 {10 scanf("%d%d",&n,&m);11 int all=1<

 

转载于:https://www.cnblogs.com/qywhy/p/9745048.html

你可能感兴趣的文章
(转)sizeof()解析和结构体内存对齐
查看>>
Android 编码规范:(三)用私有构造器或者枚举类型强化Singleton属性
查看>>
Linux中环境设置文件
查看>>
string byte 互转
查看>>
编译 apache-log4cxx-0.10.0inputstreamreader.cpp:66: error: ‘memmove’ was not declared in this sco...
查看>>
使用DLL中的资源
查看>>
servlet
查看>>
打印后台程序服务没有启动,每次打开Powerdesigner都会要我安装打印机
查看>>
iframe自动适应高度
查看>>
Git-Git Book阅读笔记
查看>>
Microsoft Excel as a Source and Target as Oracle in ODI
查看>>
.NET VS2012 将代码同步上传到 oschina.net 和 github
查看>>
让自己的网站实现在线编辑office文档
查看>>
IOS开发之功能模块--给任意的UIView添加点击事件
查看>>
php获取本周周一、周日时间,上周周一、周日时间,本月第一天,本月最后一天,上个月第一天,最后一天...
查看>>
[Android] 如何查看apk需要支持的Android版本
查看>>
mysql创建数据库
查看>>
R 语言 Windows 环境 安装与Windows下制作R的package--Rtools
查看>>
【转】Understanding Inversion of Control, Dependency Injection and Service Locator Print
查看>>
Create rolling monthly, weekly and daily Logstash indices
查看>>