博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【最大点独立集】【poj1419】【Graph Coloring】
阅读量:6456 次
发布时间:2019-06-23

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

题意:

最多能选取多少点,没有边相连。

解法:

取反图,求最大团

代码:

#include
#include
#include
using namespace std;const int maxn=11000;int e,ans,res,n,m,head[110],nxt[maxn],pnt[maxn],color[110],ansa[110];bool vis[110];void AddEdge(int u,int v){ nxt[e]=head[u];pnt[e]=v;head[u]=e++; nxt[e]=head[v];pnt[e]=u;head[v]=e++;}void DFS(int u,int cnt){ if(u==n+1) { if(cnt>ans) { ans=cnt; memcpy(ansa,color,sizeof(color)); } return; } bool can=true; for(int i=head[u];i!=-1;i=nxt[i]) if(color[pnt[i]]) { can=false; break; } if(can) { color[u]=1; DFS(u+1,cnt+1); color[u]=0; } if(cnt+n-u>ans) DFS(u+1,cnt);}int main(){ int T; scanf("%d",&T); while(T--) { ans=e=0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for(int i=0;i

转载于:https://www.cnblogs.com/zy691357966/p/5480343.html

你可能感兴趣的文章
Redis详解
查看>>
论程序员加班的害处
查看>>
codeblocks快捷键
查看>>
基于HTML5的WebGL设计汉诺塔3D游戏
查看>>
WPF资料链接
查看>>
过滤DataTable表中的重复数据
查看>>
prepare for travel 旅行准备
查看>>
再次更新
查看>>
微服务学习笔记二:Eureka服务注册发现
查看>>
C# 获取编码
查看>>
mysql的数据类型int、bigint、smallint 和 tinyint取值范围
查看>>
利用网易获取所有股票数据
查看>>
移动铁通宽带上网设置教程
查看>>
Python算法(含源代码下载)
查看>>
利用Windows自带的Certutil查看文件MD5
查看>>
通过原生js添加div和css
查看>>
简单的导出表格和将表格下载到桌面上。
查看>>
《ArcGIS Engine+C#实例开发教程》第一讲桌面GIS应用程序框架的建立
查看>>
JAVA - 大数类详解
查看>>
查询指定名称的文件
查看>>