1925_算法设计例题:最大团(回溯、分枝限界)

2022-5-16 18:17| 发布者: Hocassian| 查看: 44| 评论: 0|原作者: 肇庆学院ACM合集

摘要:
C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504153774099-Problem List-采集的数据-后羿采集器.html

Pro.ID

1925

Title

算法设计例题:最大团(回溯、分枝限界)

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1925

AC

228

Submit

740

Ratio

30.81%

时间&空间限制

  • Time Limit: 4000/2000 MS (Java/Others)     Memory Limit: 65536/32768 K (Java/Others)
  • 描述

    给定无向图G=(V,E)。如果UV,且对任意u, v ∈ U 有 (u,v) ∈ E,则称U是G的完全子图。G的完全子图U是G的团,当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。

    输入

    输入的第一行为测试样例的个数T ,接下来有T个测试样例。每个测试样例的第一行是 顶点数n 和 边数m ( n ≤ 20,m ≤ 400 ),接下来m行,每行两个整数u和v,表示顶点u和v之间有一条边相连。( 1 ≤ u < v ≤ n )。

    输出

    Description

    给定无向图G=(V,E)。如果UV,且对任意u, v ∈ U 有 (u,v) ∈ E,则称U是G的完全子图。G的完全子图U是G的团,当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。

    Input

    输入的第一行为测试样例的个数T ,接下来有T个测试样例。每个测试样例的第一行是 顶点数n 和 边数m ( n ≤ 20,m ≤ 400 ),接下来m行,每行两个整数u和v,表示顶点u和v之间有一条边相连。( 1 ≤ u < v ≤ n )。

    Output

    对应每个测试样例输出两行,第一行格式为"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

    Author

    样例输入

    1
    5 7
    1 2
    1 4
    1 5
    2 3
    2 5
    3 5
    4 5

    样例输出

    Case 1: 3

    提示

    作者


    路过

    雷人

    握手

    鲜花

    鸡蛋

    最新评论

    返回顶部