首页 > 搜索 > DFS搜索 > HDU 1530 Maximum Clique-动态规划-[解题报告] C++
2013
12-12

HDU 1530 Maximum Clique-动态规划-[解题报告] C++

Maximum Clique

问题描述 :

Given a graph G(V, E), a clique is a sub-graph g(v, e), so that for all vertex pairs v1, v2 in v, there exists an edge (v1, v2) in e. Maximum clique is the clique that has maximum number of vertex.

输入:

Input contains multiple tests. For each test:

The first line has one integer n, the number of vertex. (1 < n <= 50)

The following n lines has n 0 or 1 each, indicating whether an edge exists between i (line number) and j (column number).

A test with n = 0 signals the end of input. This test should not be processed.

输出:

One number for each test, the number of vertex in maximum clique.

样例输入:

5
0 1 1 0 1
1 0 1 1 1
1 1 0 1 1
0 1 1 0 1
1 1 1 1 0
0

样例输出:

4

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define debug puts("here")
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define foreach(i,vec) for(unsigned i=0;i<vec.size();i++)
#define pb push_back
#define RD(n) scanf("%d",&n)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define All(vec) vec.begin(),vec.end()
#define MP make_pair
#define PII pair<int,int>
#define PQ priority_queue
#define cmax(x,y) x = max(x,y)
#define cmin(x,y) x = min(x,y)
#define Clear(x) memset(x,0,sizeof(x))
/*

#pragma comment(linker, "/STACK:1024000000,1024000000")

int size = 256 << 20; // 256MB
char *p = (char*)malloc(size) + size;
__asm__("movl %0, %%esp\n" :: "r"(p) );

*/

char IN;
bool NEG;
inline void Int(int &x){
    NEG = 0;
    while(!isdigit(IN=getchar()))
        if(IN=='-')NEG = 1;
    x = IN-'0';
    while(isdigit(IN=getchar()))
        x = x*10+IN-'0';
    if(NEG)x = -x;
}
inline void LL(ll &x){
    NEG = 0;
    while(!isdigit(IN=getchar()))
        if(IN=='-')NEG = 1;
    x = IN-'0';
    while(isdigit(IN=getchar()))
        x = x*10+IN-'0';
    if(NEG)x = -x;
}

/******** program ********************/

const int MAXN = 50;

int g[MAXN][MAXN],n;
bool use[MAXN];
int dp[MAXN],best;
//int pre[MAXN],path[MAXN]; // 记录路径

bool dfs(int *id,int top,int cnt){
    if(!top){
        if(best<cnt){
            //copy( pre+1,pre+cnt+1,path ); // 记录路径
            best = cnt;
            return true;
        }
        return false;
    }
    int a[MAXN];
    rep(i,top){
        if(cnt+top-i<=best)return false;
        if(cnt+dp[id[i]]<=best)return false;
        //pre[cnt] = id[i]; // 记录路径
        int k = 0;
        for(int j=i+1;j<top;j++)
            if(g[id[i]][id[j]])
                a[k++] = id[j];
        if(dfs(a,k,cnt+1))return true;
    }
    return false;
}

inline int solve(){
    int id[MAXN];
    best = 0;
    for(int i=n-1;i>=0;i--){
        int top = 0;
        for(int j=i+1;j<n;j++)
            if(g[i][j])
                id[top++] = j;
        dfs(id,top,1);
        dp[i] = best;
    }
    return best;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("sum.in","r",stdin);
    //freopen("sum.out","w",stdout);
#endif

    while(1){
        Int(n);
        if(!n)break;
        rep(i,n)
            rep(j,n)
                Int(g[i][j]);
        cout<<solve()<<endl;
    }

    return 0;
}

解题报告转自:http://www.cnblogs.com/yejinru/p/3320937.html


  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. bottes vernies blanches

    I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。