結果

問題 No.519 アイドルユニット
コンテスト
ユーザー OUDON
提出日時 2017-10-05 16:59:00
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,009 bytes
コンパイル時間 1,604 ms
コンパイル使用メモリ 177,488 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-16 21:10:53
合計ジャッジ時間 2,761 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF   = 1e9;
const ll  INFLL = 1e18;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

struct Edge { 
    int to, cap, rev, cost; 
    Edge (int _to, int _cap, int _rev, int _cost) : to(_to), cap(_cap), rev(_rev), cost(_cost) {}
};

class MinCostFlow {
public:
    int N;
    vector<vector<Edge>> G;
    vector<int> dist, prevv, preve;

    MinCostFlow(int _n) : N(_n), G(_n, vector<Edge>()), dist(vector<int>(_n)),
        prevv(vector<int>(_n)), preve(vector<int>(_n)) {}

    void add_edge(int from, int to, int cap, int cost)
    {
        G[from].push_back({to, cap, (int)G[to].size(), cost});
        G[to].push_back({from, 0, (int)G[from].size()-1, -cost});
    }

    int min_cost_flow(int s, int t, int f)
    {
        int res = 0;
        while (f > 0) {
            fill(dist.begin(), dist.end(), INF);
            dist[s] = 0;
            bool update = true;
            while (update) {
                update = false;
                for (int v=0; v<N; v++) {
                    if (dist[v] == INF) continue;
                    for (int i=0; i<(int)G[v].size(); i++) {
                        Edge &e = G[v][i];
                        if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
                            dist[e.to] = dist[v] + e.cost;
                            prevv[e.to] = v;
                            preve[e.to] = i;
                            update = true;
                        }
                    }
                }
            }
            if (dist[t] == INF) return -1;

            int d = f;
            for (int v=t; v!=s; v=prevv[v]) {
                d = min(d, G[prevv[v]][preve[v]].cap);
            }
            f -= d;
            res += d * dist[t];
            for (int v=t; v!=s; v=prevv[v]) {
                Edge &e = G[prevv[v]][preve[v]];
                e.cap -= d;
                G[v][e.rev].cap += d;
            }
        }
        return res;
    }
};

int main()
{
    ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector<vector<int>> F(N, vector<int>(N));
    rep(i, N) rep(j, N) {
        cin >> F[i][j];
    }

    MinCostFlow mf(2*N + 2);
    const int SOURCE = 2*N;
    const int SINK   = 2*N + 1;
    const int MAX_F = 1000;

    rep(i, N) {
        mf.add_edge(SOURCE, i, 1, 0);
        mf.add_edge(N+i, SINK, 1, 0);
    }

    rep(i, N) rep(j, N) {
        if (i == j) continue;
        mf.add_edge(i, N+j, 1, MAX_F - F[i][j]);
    }

    cout << (MAX_F * N - mf.min_cost_flow(SOURCE, SINK, N)) / 2 << endl;
}
0