結果
| 問題 | No.519 アイドルユニット |
| ユーザー |
 yukudo
|
| 提出日時 | 2017-05-28 22:43:43 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,584 bytes |
| コンパイル時間 | 1,270 ms |
| コンパイル使用メモリ | 163,180 KB |
| 実行使用メモリ | 12,036 KB |
| 最終ジャッジ日時 | 2023-10-21 14:26:50 |
| 合計ジャッジ時間 | 5,742 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge9 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
ソースコード
#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;
}