SRM617D1Med PieOrDolphin
こういうのを落とすのはダメ
問題概要(原文)
$50$ 人の人がいる．
$M$ 日間，毎日りんごとオレンジの $2$ つを送ることにした． $i$ 日目には $f_i$ の人か $t_i$ の人に渡せる．
$i$ 番目の人にについて，りんごをもらった数を $a_i$ オレンジをもらった数を $b_i$ として $\sum_{i = 1}^{50} |a_i-b_i|$ を最小化するような割当てを考えよ．
考察
以下のように言い換えよう．
$M$ 本の無向辺に向き付けをする． 頂点 $i$ の出次数をを $a_i$ 入次数を $b_i$ として $\sum_{i = 1}^{50} |a_i-b_i|$ を最小化するような向き付けを示せ．
無向グラフの時点で，次数が奇数の頂点は必ずコストが $1$ 以上かかる．偶数の頂点は必ずコストが $0$ 以上になる．
ここで，ある連結成分について，全ての頂点の次数が偶数のとき，オイラー閉路が存在することに着目すると，この連結成分に属する各頂点のコストの和は $0$ である．
次数が奇数の頂点が存在する場合について考えよう．次数が奇数の頂点から移動が可能な限り移動する，ということを繰り返したとき，終了した頂点の元々の次数は必ず奇数である(握手補題よりある連結成分に存在する次数が奇数の頂点は偶数個ある)．
そこで，適当な無向グラフを構築し，次数が奇数の点それぞれからについてdfsをする．その後全ての頂点から再びdfsをすればよい．
辺を適切に削除すると $O(M)$ しなくても $O(M^2)$ で間に合う．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class PieOrDolphin
{
public int[] Distribute(int[] from, int[] to)
{
var d = new int[50];
var m = from.Length;
var ans = new int[m];
var G = Enumerate(50, x => new List<int>());
for (int i = 0; i < m; i++)
{
G[from[i]].Add(i);
G[to[i]].Add(i);
d[from[i]]++; d[to[i]]++;
}
var val = new int[50];
Func<int, int> dfs = null;
dfs = cur =>
{
while (G[cur].Count > 0)
{
var id = G[cur][G[cur].Count - 1];
G[cur].RemoveAt(G[cur].Count - 1);
if (ans[id] != 0) continue;
var f = from[id];
var t = to[id];
if (f == cur) ans[id] = 1;
else { ans[id] = 2; Swap(ref f, ref t); }
d[f]--; d[t]--;
return dfs(t);
}
return 0;
};
for (int i = 0; i < 50; i++)
if (d[i] % 2 != 0) dfs(i);
for (int i = 0; i < 50; i++)
if (d[i] != 0) dfs(i);
return ans;
}
static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
}
コメント
- こういう問題を解けないのは反省
