Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

直接用回溯就可以

Posted by lizimeng at 2016-06-04 22:38:54 on Problem 1419
这是一个最大独立集问题,是一个np完全问题,目前没有多项式时间内的确定性算法。我用的是最简单的回溯算法,没有剪枝的策略。就是顺序的考虑节点,考虑第一个节点能不能加入,分成两种情况,然后在前面的基础上考虑下一个节点。最差时间复杂度是指数级的,但是我跑出来是16ms。所以说,这道题的数据并不那么bt。
当然这道题可以转化为最大团问题,最大团问题有一个bk算法,带动态规划,效果应该会更好。

贴上我的代码和大家分享:

#include <stdio.h>
#include <stdlib.h>
#define MAXN 100

char graph[MAXN][MAXN];
int n;
int best[MAXN],best_n;
int cur[MAXN],cur_n;

void backtrack(int node)
{
    int i;
    if(node>=n)
    {
        if(cur_n > best_n)
        {
            for(i=0;i<cur_n;i++)
                best[i] = cur[i];
            best_n = cur_n;
        }
        return ;
    }

    for(i=0;i<cur_n;i++)
        if(graph[node][cur[i]])
            break;
    if(i==cur_n)
    {
        cur[cur_n++] = node;
        backtrack(node+1);
        cur_n--;
        backtrack(node+1);
    }
    else
        backtrack(node+1);

}

int main()
{
    int T;
    int k;
    int t1,t2;
    int i,j;

    scanf("%d",&T);
    while(T>0)
    {
        scanf("%d%d",&n,&k);
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                graph[i][j] = 0;
        for(i=0;i<k;i++)
        {
            scanf("%d%d",&t1,&t2);
            graph[t1-1][t2-1] = 1;
            graph[t2-1][t1-1] = 1;
        }
        best_n = 0;
        cur_n = 0;
        backtrack(0);
        printf("%d\n",best_n);
        for(i=0;i<best_n;i++)
            printf("%d ",best[i]+1);
        printf("\n");
        T--;
    }

    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator