2531Network Saboteur

这道题看了人家的题解的，不过中心思想跟人家不一样

我的ACCEPT代码

#include "iostream"
#include "algorithm"
#include "string.h"
using namespace std;
int set[120],map[120][120],MAX,n,top;

int count(){
  int total=0,i,j;
  for(i=1;i<=n;i++){
    if(set[i]==0)continue;
    for(j=1;j<=n;j++){
      if(set[j]==0)total+=map[i][j];
    }
  }
  return total;
}

void dfs(int a){
  int i;
  set[a]=1;
  if(MAX<count())MAX=count();
  for(i=a+1;i<=n;i++){
    dfs(i);
  }
  set[a]=0;
}

int main(){
  int i,j;
  cin>>n;
  for(i=1;i<=n;i++){
    for(j=1;j<=n;j++){
      cin>>map[i][j];
    }
  }
  memset(set,0,sizeof(set));
  MAX=0;
  dfs(0);
  cout<<MAX<<endl;
}

人家的代码，跟dp中的状态压缩差不多，很经典

// POJ2531.cpp : Defines the entry point for the console application.
//

#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
    int N;
    cin >> N;

    int d[21][21];
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            scanf("%d", &d[i][j]);

    int set[21];
    memset(set, 0, sizeof(set));

    int MAX = 1 << (N - 1);
    int maxflow = 0;
    for (int i = 0; i < MAX; ++i)
    {
        //set combination
        ++set[0];
        for (int j = 0; j < N; ++j)
            if (set[j] == 2){ set[j] = 0; ++set[j + 1];}
            else break;

        int cnt = 0;
        for (int j = 0; j < N; ++j)
        {
            if (set[j] == 0)continue;
            for (int k = 0; k < N; ++k)
                if (set[k] == 0)cnt += d[j][k];
        }

        if (cnt > maxflow) maxflow = cnt;
    }

    cout << maxflow << endl;
    return 0;
}