HDU5952 dfs+剪枝
2024-09-08 17:05:30
题目分析:
对于给出的n个点和m条边,求这个图的完全联通子图的数量(每次查询的子图的大小为s),对于本题而言,很容易想到的是dfs暴力和这个点相连的所有的点,并且判断这个图是否是度为s 的完全联通子图,但是如果不作任何处理的话会超时,这里需要合理选择剪枝,排除不可能的查询
注意点:
1.用in[i]数组表示编号为i的点的度,对于每次判断,如果这个点的度小于s-1这个点就直接放弃
2.对于边之间的关系,u and v (1 ≤ u < v ≤ N),所以对于每次查询,我们从小往大的编号查询即可,这样将无向图转化为有向图减少了查询的次数
3.对于每个编号的有连线的点通过vector存储,这样查询的时候直接查询和这个被选中的点相连的点是否能加入完全联通子图即可
代码:
#include<iostream>
#include<vector>
#include<string.h>
using namespace std; int mat[][];
int set[];
int in[];
vector<int>edge[];
int ans, s, n, m; void dfs(int last, int num){
if(in[last] < s-) return;
if(num == s){
ans++;
return;
}
for(int i = ; i < edge[last].size(); i++){
int x = edge[last][i];
if(in[x] < s-) continue;
int j;
for(j = ; j <= num; j++){
int from = set[j];
int to = x;
if(mat[from][to] == ) break;
}
if(j > num){
set[num+] = x;
dfs(x, num+);
}
}
} int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%d%d%d", &n, &m, &s);
for(int i = ; i <= n; i++) edge[i].clear();
memset(mat, , sizeof(mat));
memset(in, , sizeof(in));
for(int i = ; i <= m; i++){
int x, y;
scanf("%d%d", &x, &y);
edge[x].push_back(y);
mat[x][y] = ;
mat[y][x] = ;
in[x]++; //保存每个点的入度 用于剪枝
in[y]++;
}
ans = ;
for(int i = ; i <= n; i++){
set[] = i; //set中第一个元素定下
dfs(i, ); //set中已经有的最后一个编号 已经在set中的编号数
}
printf("%d\n", ans);
}
return ;
}
最新文章
- <;<;<; 判断提交方式是get还是post
- 基于SWFUpload的angular上传组件
- Docker镜像的创建、存出、载入
- Part 82 to 85 Talking about Generic queue, stack collection class
- [DevExpress]GridControl 同步列头checkbox与列中checkbox状态
- cenots 下的 lamp(备份与恢复)
- SQL高级优化之经常使用的优化策略-2(The Return Of The King)
- XML的基本操作
- AXI总线
- fastjson的常用使用方法
- 《高性能javascript》学习总结
- BZOJ 3270: 博物馆 [概率DP 高斯消元]
- python之路5-函数
- 通过java代码往mysql数据库中写入日期相关数据少13个小时
- Java Web解决跨域请求
- 在CentOS 7上安装和使用GlusterFS
- mtr命令详解诊断网络路由
- CentOS安装Yarn只需两步就搞定
- 人生第一次JAVA编程,电梯(并不算完成版),以及IDEA里使用git
- 【Python】【Web.py】详细解读Python的web.py框架下的application.py模块
热门文章
- Codeforces Round #530 (Div. 2) F 线段树 + 树形dp(自下往上)
- 线段树模板(无lazy优化)
- IAR环境搭建
- win7 64位平台编译的程序在XP 32位平台无法运行的解决方法
- 【微信小程序】小程序中的函数节流
- C# HTTP系列4 HttpWebRequest.CookieContainer属性
- Visual Studio 调试系列4 单步后退来检查旧应用状态(使用使用 IntelliTrace 窗口)
- Linux 启动数据库报错:could not open parameter file init**.ora
- 在onclick事件中传递对象参数
- layui排序功能