E - Counting Cliques HDU - 5952

題意：

給你n個(gè)點(diǎn)，m個(gè)邊，還有一個(gè)s，問這個(gè)圖中有多少個(gè)等于s的點(diǎn)集可以組成一個(gè)完全圖

題解：

這題。。直接暴力搜索就行
分析復(fù)雜度的時(shí)候，應(yīng)該考慮只有1000條邊，所以我最多才枚舉1000條邊，100個(gè)點(diǎn)，再加上每次判斷最多1e6的時(shí)間復(fù)雜度，再加一些剪枝，肯定不會(huì)超時(shí)的
如何避免搜索重復(fù)呢？我們規(guī)定起點(diǎn)標(biāo)號(hào)小于終點(diǎn)標(biāo)號(hào)，這樣邊就成為單向邊，不會(huì)反過來跑，這樣實(shí)現(xiàn)剪枝且避免重復(fù)計(jì)算
具體實(shí)現(xiàn)為：我依次枚舉每個(gè)點(diǎn)在完全圖內(nèi)，然后從這個(gè)點(diǎn)開始出發(fā)跑，每到一個(gè)新點(diǎn)，判斷他是否與已經(jīng)存的所有點(diǎn)都有邊，都有邊說明他也在完全圖中，加入，然后繼續(xù)，直到滿足s個(gè)點(diǎn)集，然后return，繼續(xù)跑
詳細(xì)看代碼

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } int n,m,s; const int maxn=130; vector<int>vec[maxn]; bool edge[maxn][maxn]; int tot=0; int vis[maxn]; void dfs(int x){if(x==s){tot++;return ;}int pre=vis[x];for(int i=0;i<vec[pre].size();i++){int f=1;int v=vec[pre][i];for(int j=1;j<=x;j++){//與之前已經(jīng)加入連通圖的點(diǎn)查看是否都有邊 if(edge[v][vis[j]]==0){f=0;break;}}if(f==1){vis[x+1]=v;dfs(x+1);} } } int main() {int t;scanf("%d",&t);while(t--){tot=0;memset(edge,0,sizeof(edge));scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);edge[u][v]=1;edge[v][u]=1;if(u<v) vec[u].push_back(v);else vec[v].push_back(u);}for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));vis[1]=i;dfs(1);}printf("%d\n",tot);for(int i=1;i<=100;i++)vec[i].clear();}return 0;}

總結(jié)

以上是生活随笔為你收集整理的E - Counting Cliques HDU - 5952的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。