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;
}