結果

問題 No.519 アイドルユニット
ユーザー はまやんはまやん
提出日時 2017-05-28 22:11:16
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,047 bytes
コンパイル時間 1,712 ms
コンパイル使用メモリ 176,464 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-21 15:29:31
合計ジャッジ時間 2,901 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27 WA * 7
権限があれば一括ダウンロードができます

ソースコード

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[25][25];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(y, 0, N) rep(x, 0, N) cin >> E[y][x];

    MinCostFlow<101, int> mcf;

    int s = N * 2, t = N * 2 + 1;
    int U = 1010;

    rep(i, 0, N) mcf.add_edge(s, i, 1, 0);
    rep(i, 0, N) rep(j, 0, N) if(i != j) mcf.add_edge(i, j + N, 1, U - E[j][i]);
    rep(i, 0, N) mcf.add_edge(N + i, t, 1, 0);

    int f = mcf.mincost(s, t, N);
    int ans = U * N / 2 - f / 2;
    //cout << f << endl;
    cout << ans << endl;

}
0