アルゴリズム設計例題:最大団(遡及、枝分かれ限界)
1933 ワード
Description
無方向図G=(V,E)が与えられる.UVであり,任意のu,v∈Uに対して(u,v)∈Eがある場合,UはGの完全サブマップと呼ぶ.Gの完全サブマップUはGのグループであり、UがGのより大きな完全サブマップに含まれていない場合のみである.Gの最大団とは、Gに含まれる頂点数が最も多い団を指す.
Input
入力された第1の動作試験サンプルの個数T、次にTの試験サンプルがある.各試験サンプルの最初の行は頂点数nと辺数m(n≦20,m≦400)であり、次にm行は、頂点uとvの間に1つの辺が接続されていることを示す2つの整数uとvである.( 1 ≤ u < v ≤ n ).
Output
各試験サンプルに対して2行出力され、第1行は「Case#:M」形式であり、ここで、'#'は第数試験サンプル(1からカウント)を表し、Mは最大団頂点数である.
Sample Input
1 5 7 1 2 1 4 1 5 2 3 2 5 3 5 4 5
Sample Output
Case 1: 3
題意分析:
完全サブマップは、図中の任意の2つの頂点が接続されており、完全マップと同じです.
例:
(a) (b) (c) (d)
図aは無方向図であり、図b、c、dはいずれも図aの団であり、いずれも最大団である.構想も非常に簡単で、毎回1つの点を図の中に入れて、無方向図なのでサブセットツリーを生成して、すべての点を図の中に入れて1回試してみるだけでいいです.
枝切り部分は簡単な枝切り、すなわち試したことのない点+図中の点を用いる
まとめ:dfsの問題をするたびにサブセットツリーを生成するかソートツリーを生成するかを判断してから、手を出し始めます.最初はコード全体がますます複雑になっているとは判断していません.サブセットツリーは各点を1回検索すればいいので、ソートツリーは再帰的に各点をforしなければなりません.(二叉木と多叉木の違い).
無方向図G=(V,E)が与えられる.UVであり,任意のu,v∈Uに対して(u,v)∈Eがある場合,UはGの完全サブマップと呼ぶ.Gの完全サブマップUはGのグループであり、UがGのより大きな完全サブマップに含まれていない場合のみである.Gの最大団とは、Gに含まれる頂点数が最も多い団を指す.
Input
入力された第1の動作試験サンプルの個数T、次にTの試験サンプルがある.各試験サンプルの最初の行は頂点数nと辺数m(n≦20,m≦400)であり、次にm行は、頂点uとvの間に1つの辺が接続されていることを示す2つの整数uとvである.( 1 ≤ u < v ≤ n ).
Output
各試験サンプルに対して2行出力され、第1行は「Case#:M」形式であり、ここで、'#'は第数試験サンプル(1からカウント)を表し、Mは最大団頂点数である.
Sample Input
1 5 7 1 2 1 4 1 5 2 3 2 5 3 5 4 5
Sample Output
Case 1: 3
題意分析:
完全サブマップは、図中の任意の2つの頂点が接続されており、完全マップと同じです.
例:
(a) (b) (c) (d)
図aは無方向図であり、図b、c、dはいずれも図aの団であり、いずれも最大団である.構想も非常に簡単で、毎回1つの点を図の中に入れて、無方向図なのでサブセットツリーを生成して、すべての点を図の中に入れて1回試してみるだけでいいです.
枝切り部分は簡単な枝切り、すなわち試したことのない点+図中の点を用いる
まとめ:dfsの問題をするたびにサブセットツリーを生成するかソートツリーを生成するかを判断してから、手を出し始めます.最初はコード全体がますます複雑になっているとは判断していません.サブセットツリーは各点を1回検索すればいいので、ソートツリーは再帰的に各点をforしなければなりません.(二叉木と多叉木の違い).
:
#include
#include
int book[25][25],vist[25],que[25];//que ,book ,vist
int n,m,maxx;
void dfs(int x,int sum){
if(x>n){// ,
maxx=sum;
return ;
}
int vt=0;
for(int j=0;jmaxx)//
dfs(x+1,sum);
}
int main(){
int t,vi=0;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
int x,y;
memset(vist,0,sizeof(vist));
memset(book,0,sizeof(book));
maxx=0;
for(int i=1;i<=m;i++){
scanf("%d %d",&x,&y);
book[x][y]=1;
book[y][x]=1;
}
dfs(1,0);
vi++;
printf("Case %d: %d
",vi,maxx);
}
return 0;
}