結果

問題 No.519 アイドルユニット
ユーザー はまやんはまやんはまやんはまやん
提出日時 2017-05-28 21:57:08
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,012 bytes
コンパイル時間 1,536 ms
コンパイル使用メモリ 168,204 KB
実行使用メモリ 82,368 KB
最終ジャッジ日時 2024-09-21 15:25:12
合計ジャッジ時間 5,954 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
template<int NV, class V> struct MinCostFlow {
    struct edge { int to, capacity; V cost; int reve;
        edge(int a, int b, V c, int d) { to = a; capacity = b; cost = c; reve = d; } };
    vector<edge> E[NV];
    int prev_v[NV], prev_e[NV]; V dist[NV];
    void add_edge(int x, int y, int cap, V cost) {
        E[x].push_back(edge(y, cap, cost, (int)E[y].size()));
        E[y].push_back(edge(x, 0, -cost, (int)E[x].size() - 1)); /* rev edge */
    }
    V mincost(int from, int to, int flow) {
        V res = 0; int i, v; rep(i, 0, NV) prev_v[i] = 0; rep(i, 0, NV) prev_e[i] = 0;
        while (flow>0) {
            fill(dist, dist + NV, numeric_limits<V>::max() / 2); dist[from] = 0;
            priority_queue<pair<int, int> > Q; Q.push(make_pair(0, from));
            while (Q.size()) { int d = -Q.top().first, cur = Q.top().second; Q.pop();
                if (dist[cur] != d) continue; if (d == numeric_limits<V>::max() / 2) break;
                rep(i, 0, E[cur].size()) {
                    edge &e = E[cur][i];
                    if (e.capacity>0 && dist[e.to]>d + e.cost) {
                        dist[e.to] = d + e.cost; prev_v[e.to] = cur; prev_e[e.to] = i;
                        Q.push(make_pair(-dist[e.to], e.to)); } } }
            if (dist[to] == numeric_limits<V>::max() / 2) return -1; int lc = flow;
            for (v = to; v != from; v = prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
            flow -= lc; res += lc*dist[to];
            for (v = to; v != from; v = prev_v[v]) { edge &e = E[prev_v[v]][prev_e[v]];
                e.capacity -= lc; E[v][e.reve].capacity += lc; } } return res;}
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/


int N;
int E[30][30];
int dp[1 << 24];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(y, 0, N) rep(x, 0, N) cin >> E[y][x];

    dp[0] = 1;
    rep(i, 0, 1 << N) if(dp[i]) {
        rep(a, 0, N) rep(b, a + 1, N) {
            if (i & (1 << a)) continue;
            if (i & (1 << b)) continue;

            int j = i + (1 << a) + (1 << b);
            dp[j] = max(dp[j], dp[i] + E[a][b]);
        }
    }

    cout << dp[(1 << N) - 1] - 1 << endl;
}
0