众创空间文化建设网站,网上国网app官方下载,wordpress媒体库显示不出来,河北省建设厅网站E - Counting Cliques HDU - 5952
题意#xff1a;
给你n个点#xff0c;m个边#xff0c;还有一个s#xff0c;问这个图中有多少个等于s的点集可以组成一个完全图
题解#xff1a;
这题。。直接暴力搜索就行 分析复杂度的时候#xff0c;应该考虑只有1000条边#…E - Counting Cliques HDU - 5952
题意
给你n个点m个边还有一个s问这个图中有多少个等于s的点集可以组成一个完全图
题解
这题。。直接暴力搜索就行 分析复杂度的时候应该考虑只有1000条边所以我最多才枚举1000条边100个点再加上每次判断最多1e6的时间复杂度再加一些剪枝肯定不会超时的 如何避免搜索重复呢我们规定起点标号小于终点标号这样边就成为单向边不会反过来跑这样实现剪枝且避免重复计算 具体实现为我依次枚举每个点在完全图内然后从这个点开始出发跑每到一个新点判断他是否与已经存的所有点都有边都有边说明他也在完全图中加入然后继续直到满足s个点集然后return继续跑 详细看代码
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
int n,m,s;
const int maxn130;
vectorintvec[maxn];
bool edge[maxn][maxn];
int tot0;
int vis[maxn];
void dfs(int x){if(xs){tot;return ;}int previs[x];for(int i0;ivec[pre].size();i){int f1;int vvec[pre][i];for(int j1;jx;j){//与之前已经加入连通图的点查看是否都有边 if(edge[v][vis[j]]0){f0;break;}}if(f1){vis[x1]v;dfs(x1);} }
}
int main()
{int t;scanf(%d,t);while(t--){tot0;memset(edge,0,sizeof(edge));scanf(%d%d%d,n,m,s);for(int i1;im;i){int u,v;scanf(%d%d,u,v);edge[u][v]1;edge[v][u]1;if(uv) vec[u].push_back(v);else vec[v].push_back(u);}for(int i1;in;i){memset(vis,0,sizeof(vis));vis[1]i;dfs(1);}printf(%d\n,tot);for(int i1;i100;i)vec[i].clear();}return 0;}
