SRM 275 DIV1 Hard SantaClaus

問題 Editorial

問題

n人の人とプレゼントがn個ある。それぞれの人の各プレゼントのスコアvalueが与えられる。
今、人iはプレゼントiに割り当てられている。
ここから、何人かでプレゼントを交換したとき、新たな各人のスコアの総和がそれをする前より増加する最少人数を求めよ。
また、その最少人数の中で最大の増加スコアを求めよ。
増加する交換のしかたがない時は(0, 0)を返せ

• 2 <= n <= 50

解答

Editorialを参考にした。
人iがプレゼントjを得る時の増加するスコアをi→jの重みとしたグラフを作る時、
(人iを含むk人で交換した時の最大スコア = 頂点iを含むサイズkの単純閉路の最大スコア)になる。
最大スコアの単純閉路の求め方だが、これはFloyd-Warshallを一回ずつすればいい。
それでg[i][i]のmaxを取る。

コメント

結構な人数が解いているのに解けなかった。
まず、swapから閉路への発想は絶対。完全2部グラフのマッチングもswapで考えることができる。
閉路はスコア最大のものを求めることもできる。ただし、同じ頂点に2回以上来うること(負閉路)に注意。
今回はkを増加させながらやっていてbreakするのでいいが、この「2回以上来ない」をきちんと制約とするとTSPになってしまうと思う。

コード

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define pb(x) push_back(x)
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
typedef vector<int> vi;
struct SantaClaus {
	vector <int> exchange(vector <string> value) {
		int n = value.size();
		static int edge[55][55];
		rep(i, n) rep(j, n) edge[i][j] = value[i][i] - value[i][j];
		static int g[2][55][55];
		int (*current)[55] = g[0], (*next)[55] = g[1];
		mset(g, INF);
		rep(i, n) next[i][i] = 0;
		rer(t, 1, n) {
			swap(current, next);
			rep(i, n) rep(j, n) {
				int x = INF;
				rep(k, n) x = min(x, current[i][k]+edge[k][j]);
				next[i][j] = x;
			}
			int r = 0;
			rep(i, n) r = min(r, next[i][i]);
			if(r < 0) {
				vi v;
				v.pb(t);
				v.pb(- r);
				return v;
			}
		}
		return vi(2, 0);
	}
};