首页 > 代码库 > HDU 5952 Counting Cliques -暴力
HDU 5952 Counting Cliques -暴力
现场赛手速三题,这题一直没写。
直接暴力,注意点只有一个!单向建边,从小点到大点。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 struct edge 6 { 7 int to; 8 int next; 9 }E[1011]; 10 int head[111]; 11 bool e[111][111]; 12 int tot; 13 int N,S,M,ans; 14 void addedge(int a,int b) 15 { 16 E[tot].to = a; 17 E[tot].next = head[b]; 18 head[b] = tot++; 19 } 20 int V[20]; 21 int sv = 0; 22 bool check(int t) 23 { 24 for (int i = 1; i<=sv;i++) 25 { 26 if (!e[V[i]][t]) return false; 27 } 28 return true; 29 } 30 void dfs(int u) 31 { 32 if (sv==S) 33 { 34 ans++; 35 return; 36 } 37 for (int i = head[u] ; i!=-1;i = E[i].next) 38 { 39 int v = E[i].to; 40 if (check(v)) 41 { 42 V[++sv] = v; 43 dfs(v); 44 sv--; 45 } 46 } 47 } 48 int main() 49 { 50 int T; 51 cin >> T; 52 while (T--) 53 { 54 cin >> N >> M >>S; 55 memset(head,-1,sizeof(head)); 56 memset(e,false,sizeof(e)); 57 tot = 0; 58 for (int i= 1; i<=M; i++) 59 { 60 int a,b; 61 scanf("%d%d",&a,&b); 62 addedge(min(a,b),max(a,b)); 63 e[a][b] = true; 64 e[b][a] = true; 65 } 66 ans=0; 67 for (int i = 1; i<=N; i++) 68 { 69 sv = 0; 70 V[++sv] = i; 71 dfs(i); 72 } 73 cout <<ans <<endl; 74 } 75 }
HDU 5952 Counting Cliques -暴力
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。