アルゴリズム設計例題:最大団(遡及、枝分かれ限界)

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しなければなりません.(二叉木と多叉木の違い).
#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; }