結果

問題 No.519 アイドルユニット
コンテスト
ユーザー yukudo
提出日時 2017-05-28 22:43:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,584 bytes
コンパイル時間 1,364 ms
コンパイル使用メモリ 161,164 KB
実行使用メモリ 13,696 KB
最終ジャッジ日時 2024-09-21 15:41:56
合計ジャッジ時間 5,962 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for (int i=0,_n=(int)(n); i < _n; i++)
template<class T> bool chkmin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool chkmax(T &a, T b) { return a < b ? (a = b, true) : false; }

typedef long long ll;
typedef int Weight;
const int N = 24;

// adj[i][j] = w(i,j)
Weight adj[N][N];
int size, sorted[N][N], num[N];
void rec(int match[], int p, int l, Weight w, Weight &opt) {
  int q = p + 1, i;
  if (w >= opt) return;
  for (; q < size; ++q) if (match[q] == -1) break;
  int m = num[q], *list = sorted[q];
  REP(j,m) if (match[i=list[j]] == -1) { // process greedily
    match[q] = i, match[i] = q;
    w += adj[i][q];
    if (l + 1 < size / 2) rec(match, q, l+1, w, opt);
    else opt = min(opt, w);
    w -= adj[i][q];
    match[q] = -1, match[i] = -1;
  }
}

const int INF = 10000000;

int gs;
bool compareWith(int i, int j) { return adj[gs][i] < adj[gs][j]; }
Weight minimumWeightMatching() {
  for (gs = 0; gs < size; ++gs) { // sort adjacent nodes by edge weight
    for (int j = gs+1; j < size; ++j)
      sorted[gs][num[gs]++] = j;
    sort(sorted[gs], sorted[gs]+num[gs], compareWith);
  }
  int match[size]; fill(match, match+size, -1);
  Weight opt = INF;
  rec(match, -1, 0, 0, opt);
  return opt;
}


int main2() {
  cin >> size;
  REP(i, size) REP(j, size) { cin >> adj[i][j]; adj[i][j] = 2000 - adj[i][j]; } 
  int ans = minimumWeightMatching();
  ans = (size/2) * 2000 - ans;
  cout << ans << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws) main2();
  return 0;
}
0