#include<bits/stdc++.h>
using namespace std;
int a[100][100];   
int x[100]; 
int n;  
int cn; 
int bestn; 

void backtrack(int i)
{
    if(i > n){
        bestn = cn;
        return;
    }
 
    int OK = 1;
    for(int j=1; j<i; j++){
        if(x[j] == 1 && a[i][j] == 0){   
            OK = 0;
            break;
        }
    }
    if(OK){ /// 进入左子树
        x[i] = 1;
        cn++;
        backtrack(i+1);
        x[i] = 0;
        cn--;
    }
    if(cn+n-i > bestn){
        x[i] = 0;
        backtrack(i+1);
    }
}

int main()
{
    int t,m,u,v;
    scanf("%d",&t);
    for(int k=1; k<=t; k++)
    {
        cn = 0;
        bestn = 0;
        memset(a,0,sizeof(a));
        scanf("%d%d",&n,&m);
        for(int j=1; j<=m; j++){
            scanf("%d%d",&u,&v);
            a[u][v] = 1;
            a[v][u] = 1;
        }
        backtrack(1);
        printf("Case %d: %d\n",k,bestn);
    }
}
//子矩阵
#include<bits/stdc++.h>
using namespace std;
int ans(int g,int q[]){
   int cut=0;
   int ch=0;
    for(int i=1;i<=g;i++){
        if(ch>0)
        ch+=q[i];
        else
        ch=q[i];
        if(ch>cut)
        cut=ch;
    }
    return cut;
}
int main(){
     int n,m;
     int i,j,k;
     int a[401][401];
     while(~scanf("%d%d",&n,&m)){
     for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        scanf("%d",&a[i][j]);
     int sum=0;
     int b[401];
     for(i=1;i<=n;i++)
     {
        for(k=1;k<=m;k++)
           b[k]=0;
      for(j=i;j<=n;j++){
        for(k=1;k<=m;k++)
            b[k]+=a[j][k];
            int Max=ans(m,b);
            if(Max>sum)
                sum=Max;
        }
        }
        printf("%d\n",sum);
    }
     return 0;
}

///是否可达

#include<bits/stdc++.h>
using namespace std;
#define MAX 1003
int q[MAX][MAX],que[MAX];
int n,e,d;

void backtrack(int x,int y)
{
    if(x==y){   ///出口
        d=1;
    }
    que[x]=1;
    for(int i=1; i<=n; i++){
        if(q[x][i]==1 && que[i]==0){
            if(i==y){    
                d=1;
            }
            backtrack(i,y);
        }
    }
}

int main()
{
    while(~scanf("%d%d",&n,&e))
    {
        int a,b,u,v,t;
        memset(q,0,sizeof(q));
        for(int i=1;i<=n;i++){
            q[i][i]=1;
        }
        for(int i=1;i<=e;i++){
            scanf("%d%d",&a,&b);
            q[a][b]=1;
        }
        scanf("%d",&t);
        while(t--)
        {
            d=0;
            memset(que,0,sizeof(que));
            scanf("%d%d",&u,&v);
            backtrack(u,v);
            if(d==1)
                printf("yes\n");
            else
                printf("no\n");
        }
        printf("\n");
    }
    return 0;
}

View Code