UVa 12923 : The Island
問題リンク : https://uva.onlinejudge.org/external/129/12923.pdf
問題概要 :
n * n のマトリックスが与えられる
マトリックスの(i,j)はi番目の人が武器jを使った時に得られる力を表す
n人の人がそれぞれ1つ武器を持った際に得られる力の総和の最大値を求めよ
武器はそれぞれ1つずつしかない
解法 :
ハンガリアンマッチングそのまま
2部グラフの辺のコストを負にして最小費用流すると良い
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; typedef pair<int,int> ii; struct Edge{ int to,cap,cost,rev; Edge(int to=0,int cap=0,int cost=0,int rev=0):to(to),cap(cap),cost(cost),rev(rev){} }; const int MAX_V = 11000, IINF = INT_MAX; int V; vector<Edge> G[MAX_V]; int h[MAX_V],dist[MAX_V],prevv[MAX_V],preve[MAX_V]; inline void add_edge(int from,int to,int cap,int cost){ G[from].push_back(Edge(to,cap,cost,G[to].size())); G[to].push_back(Edge(from,0,-cost,G[from].size()-1)); } int min_cost_flow(int s,int t,int f){ int res = 0; fill(h,h+V,0); while(f>0){ priority_queue<ii,vector<ii>,greater<ii> > Q; fill(dist,dist+V,IINF); dist[s] = 0; Q.push(ii(0,s)); while(!Q.empty()){ ii p = Q.top(); Q.pop(); int v = p.second; if( dist[v] < p.first ) continue; for(int i=0;i<G[v].size();i++){ Edge &e = G[v][i]; if( e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to] ) { dist[e.to] = dist[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v; preve[e.to] = i; Q.push(ii(dist[e.to],e.to)); } } } if( dist[t] == IINF ) return -1; rep(v,V) h[v] += dist[v]; 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 * h[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(){ int n; while( cin >> n ){ V = n * 2 + 2; rep(i,V) G[i].clear(); int source = n * 2; int sink = source + 1; rep(i,n) { add_edge(source,i,1,0); add_edge(n+i,sink,1,0); } int w; rep(i,n) rep(j,n) { cin >> w; add_edge(i,n+j,1,-w); } cout << -min_cost_flow(source,sink,n) << endl; } return 0; }