TopCoder SRM 371 SRM Div1 Medium ChessMatchup

問題

n人のチェスのチームが二つある。
自軍のそれぞれの人の強さはus[i]で表され、敵軍のそれぞれの人の強さはthem[i]で表される。

それぞれのチームからn人を順番に出し、勝負（強さの大きい人が必ず勝つ。強さが同じなら引き分け）をして、
勝ったら2点、引き分けなら1点がもらえる。

相手のn人を出してくる順番がわかっているとき、
自軍は最大で何点を得られるか、求めよ。

制約条件

n≦50

方針

自軍のi番目の人と敵軍のj番目の人が戦ったときに自軍に得られる得点をs[i][j]としたとき、
自軍のi番目の人に相当する頂点から敵軍のj番目の人に相当する頂点に、
コスト-s[i][j], 容量1の辺を張ると、
得られる最大のスコアはこのグラフの最小費用流になっている。

なので、最小費用流問題を解けばよい。

ソースコード

費用流は蟻本実装。

const int MAX_V=102;
struct edge{ int to,cap,cost,rev; };
int V;
vector<edge> G[MAX_V];
int dist[MAX_V], prevv[MAX_V], preve[MAX_V];

void add_edge(int from,int to,int cap,int cost){
	G[from].pb((edge){to, cap, cost, G[to].size()});
	G[to].pb((edge){from, 0, -cost, G[from].size()-1});
}
int min_cost_flow(int s,int t,int f){
	int res=0;
	while(f>0){
		fill(dist,dist+V,inf);
		dist[s]=0;
		bool update=1;
		while(update){
			update=0;
			rep(v,V){
				if(dist[v]==INF)continue;
				rep(i,G[v].size()){
					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=1;
					}
				}
			}
		}
		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;
}

class ChessMatchup {
	public:
	int maximumScore(vector <int> us, vector <int> them) 
	{
		int n=us.size();
		V=n*2+2;
		rep(i,V)G[i].clear();
		rep(i,n)rep(j,n)
			add_edge(i,j+n,1,us[i]==them[j]?1:us[i]<them[j]?2:0);
		rep(i,n)add_edge(V-2,i,1,0), add_edge(i+n,V-1,1,0);
		return n*2-min_cost_flow(V-2,V-1,n);
	}
};