UVa-10746 : Crime Wave - The Sequel
問題概要
コストがdoubleとなる最小重み最大2部マッチングを求める問題。
解法
最小費用流。
acceptされたコード
#include <cstdio> #include <queue> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef pair<double, int> P; struct edge{ int to, cap, rev; double cost; edge(int to_, int cap_, int rev_, double cost_):to(to_), cap(cap_), rev(rev_), cost(cost_){} }; const int MAX_V = 500; const double EPS = 1e-6; const double INF = 1e100; void add_edge(int from, int to, int cap, double cost){ G[from].push_back(edge(to,cap,G[to].size(), cost)); G[to].push_back(edge(from,0,G[from].size()-1, -cost)); } void init(){ V = N + M + 2; source = N + M; sink = source + 1; for(int i=0; i<V; i++){ G[i].clear(); } for(int i=0; i<N; i++){ add_edge(source, i, 1, 0); } for(int i=0; i<M; i++){ add_edge(N+i, sink, 1, 0); } for(int i=0; i<N; i++){ for(int j=0; j<M; j++){ double f; scanf("%lf", &f); add_edge(i, N+j, 1, f); } } } int main(){ while(scanf("%d%d",&N,&M), N){ init(); printf("%.2f\n", min_cost_flow(source, sink, N)/N + EPS); } return 0; }