結果

問題 No.519 アイドルユニット
ユーザー kurenai3110
提出日時 2017-06-04 04:07:04
言語 C++11
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,909 bytes
コンパイル時間 869 ms
コンパイル使用メモリ 86,172 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-22 04:48:32
合計ジャッジ時間 1,970 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 27 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <functional>
using namespace std;

static const int INF = 1e9;
struct MinCostFlow {
	struct E {
		//to,容量,コスト,逆辺のindex
		int to, cap, cost, rev;
		E(int t, int ca, int co, int r) {
			to = t;
			cap = ca;
			cost = co;
			rev = r;
		}
	};

	//最大頂点数
	int V;
	vector<vector<E>>G;
	MinCostFlow(int v) {
		V = v;
		G.resize(V);
	}

	//有向辺
	inline void add_edge(int from, int to, int cap, int cost) {
		if (from == to)return;
		E e = E(to, cap, cost, G[to].size());
		E ee = E(from, 0, -cost, G[from].size());
		G[from].push_back(e);
		G[to].push_back(ee);
	}

	//コストを距離とみる
	//コスト,最小コスト
	vector<int>dist, mindist;
	//パス復元用
	vector<int>pre_v, pre_i;

	//始点から各頂点までの最小コスト
	void dijkstra(int s) {
		priority_queue< pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > que;
		dist.assign(V, INF);
		dist[s] = 0;
		que.push(pair<int, int>(0, s));
		while (!que.empty()) {
			pair<int, int> p = que.top(); que.pop();
			int v = p.second;
			if (dist[v] < p.first)continue;

			for (int i = 0; i < G[v].size(); i++) {
				E &e = G[v][i];
				if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + mindist[v] - mindist[e.to]) {
					dist[e.to] = dist[v] + e.cost + mindist[v] - mindist[e.to];
					pre_v[e.to] = v;
					pre_i[e.to] = i;
					que.push(pair<int, int>(dist[e.to], e.to));
				}
			}
		}
	}

	//最小費用を返す
	int min_cost_flow(int s, int t, int flow) {
		int cost = 0;
		mindist.resize(V);
		pre_v.resize(V);
		pre_i.resize(V);

		//フローを流しつくすまで
		while (flow > 0) {
			dijkstra(s);
			//もう流せなかったら
			if (dist[t] == INF)return -1;

			//最小コストの更新
			for (int v = 0; v < V; v++)mindist[v] += dist[v];

			//最小コストパス上の最大流
			int f = flow;
			for (int v = t; v != s; v = pre_v[v]) {
				f = min(f, G[pre_v[v]][pre_i[v]].cap);
			}
			flow -= f;

			//費用の更新
			cost += f * mindist[t];

			//容量の更新
			for (int v = t; v != s; v = pre_v[v]) {
				E& e = G[pre_v[v]][pre_i[v]];
				E& ee = G[v][e.rev];
				e.cap -= f;
				ee.cap += f;
			}
		}

		return cost;
	}
};

int main()
{
	int n; cin >> n;
	vector<vector<int>>F(n);

	int maxF = 0;
	for (int i = 0; i < n; i++) {
		F[i].resize(n);
		for (int j = 0; j < n; j++) {
			cin >> F[i][j];
			maxF = max(maxF, F[i][j]);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			F[i][j] = maxF - F[i][j];
		}
	}

	MinCostFlow mcf(2 * n + 2);
	for (int i = 0; i < n; i++) {
		mcf.add_edge(0,i+1,1,0);
		for (int j = 0; j < n; j++) {
			mcf.add_edge(i+1,n+j+1,1,F[i][j]);
		}
		mcf.add_edge(n + i + 1, 2*n + 1, 1, 0);
	}

	int ans = mcf.min_cost_flow(0, 2*n+1,n);

	cout << (n/2)*maxF-ans/2 << endl;

    return 0;
}
0