[BOJ]14889番スタートとリンク

13482 ワード
アルゴリズム#アルゴリズム# brute force テキストリンク

问题的短片


に近づく


最初はteam 1に全員を割り当て、組合せを探す過程でteam 2に移動します.N+1長の一次元配列を作成し,0と1をそれぞれチームに属する,チームに属さない状態とした.そしてコンビネーションが完了した後、チーム1とチーム2の能力値を加えて、両チームの能力値の差が最も小さい場合を求めた.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define INF 987654321

int N;
int arr[21][21] = {0};
int team1[21] = {0}, team2[21] = {0};
bool visited[21] = {false};
int sum1 = 0, sum2 = 0;
int minval = INF;

void combination(int s) {
  team1[s] = 0; // move 's' to team2
  team2[s] = 1;

  if(count(team1 + 1, team1 + N + 1, 1) == N / 2) {
    sum1 = sum2 = 0;

    for(int i = 1; i <= N; i++) {
      if(!team1[i]) continue;
      for(int j = 1; j < i; j++) {
        if(!team1[j]) continue;
        sum1 = sum1 + arr[i][j] + arr[j][i];
      }
    }

    for(int i = 1; i <= N; i++) {
      if(!team2[i]) continue;
      for(int j = 1; j < i; j++) {
        if(!team2[j]) continue;
        sum2 = sum2 + arr[i][j] + arr[j][i];
      }
    }

    minval = min(minval, abs(sum1 - sum2));
    return;
  }

  for(int i = s; i <= N; i++) {
    if(!visited[i]) {
      visited[i] = true;
      combination(i);
      team1[i] = 1;
      team2[i] = 0;
      visited[i] = false;
    }
  }
}

int main() {
  std::ios::sync_with_stdio(false);

  cin >> N;
  for(int i = 1; i <= N; i++) {
    for(int j = 1; j <= N; j++)
      cin >> arr[i][j];
    team1[i] = 1;
  }

  combination(1);
  cout << minval;
}
[JAVA]SWEA 5215-ハンバーグダイエット
Go: Hello, Go