結果
問題 | No.519 アイドルユニット |
ユーザー |
![]() |
提出日時 | 2017-05-28 22:51:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,428 bytes |
コンパイル時間 | 1,643 ms |
コンパイル使用メモリ | 170,052 KB |
実行使用メモリ | 16,952 KB |
最終ジャッジ日時 | 2024-09-21 15:43:23 |
合計ジャッジ時間 | 6,044 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 1 -- * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;#define REP(i,n) for(int i=0;i<(int)n;++i)#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)#define ALL(c) (c).begin(), (c).end()typedef int Weight;const int N = 50;const int INF = 1 << 25;Weight adj[N][N];int sz, sorted[N][N], num[N];int match[N];void rec(int match[], int p, int l, Weight w, Weight &opt) {int q = p + 1, i;// if(w >= opt) return;for(; q < sz; ++q) if(match[q] == -1) break;int m = num[q], *list = sorted[q];REP(j, m) if(match[i = list[j]] == -1) { // process greedilymatch[q] = i, match[i] = q;w += adj[i][q];if(l + 1 < sz / 2) rec(match, q, l + 1, w, opt);else opt = min(opt, w);w -= adj[i][q];match[q] = -1, match[i] = -1;}}int gs;bool compareWith(int i, int j) { return adj[gs][i] < adj[gs][j]; }Weight minimumWeightMatching() {for(gs = 0; gs < sz; ++gs) { // sort adjacent nodes by edge weightfor(int j = gs + 1; j < sz; ++j)sorted[gs][num[gs]++] = j;sort(sorted[gs], sorted[gs] + num[gs], compareWith);}fill(match, match + sz, -1);Weight opt = INF;rec(match, -1, 0, 0, opt);return opt;}int main() {cin.tie(0);ios::sync_with_stdio(false);cin >> sz;for(int i = 0; i < sz; i++) {for(int j = 0; j < sz; j++) {cin >> adj[i][j];adj[i][j] *= -1;if(i == j) adj[i][j] = INF;}}cout << -minimumWeightMatching() << endl;}