JOI2013春合宿Day4 プレゼント(Presents)

問題

http://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day4.pdf

解法

有向グラフをイメージしてみます。
人々の要望(同じ/違うお菓子をもらいたい)を全て満たせないのはどういう場合でしょうか。

今回、辺というのは自分と自分がお菓子をもらう人の関係でしかないので、一度辺の向きを無視して全ての辺を無向辺に変換して考えてみます。

すると、この無向グラフ上での閉路になっていない部分では全ての人の要望が満たせることがわかります。
(※本家の解説通り、無向グラフとして考えたときの閉路をサイクルと呼ぶことにします。)
貪欲的にお互いの関係を決めていけばいいからです。
しかし、サイクルがある場合はどうでしょう。
実はサイクル内で矛盾が生じる場合があります。
サイクル内で違うお菓子をもらいたいという人が偶数人なら矛盾は生じません。(偶数回反転するイメージ)
つまり、サイクルの中で違うお菓子をもらいたい人が奇数人の場合でも、そのサイクルに含まれる1人が自分の要望を我慢すればサイクル内で平和が訪れます。(違うお菓子をもらいたい人が同じお菓子をもらう/その逆)

サイクル内で誰が我慢するかは、なるべく我慢しても損しない人を貪欲的に選べば良さそうに見えます。
でもサイクルとサイクルが重なってしまう場合はそんな貪欲ではうまくいきませんね。
でも、しかし、実はサイクルとサイクルが重なってしまう場合はありません。

基本に立ち返って有向グラフとして考えてみます。

各頂点からの出力辺はたかだか1つまでなので、頂点たちがサイクルを作るとなると有向グラフ上での閉路を作るしかないです。
(実はサイクル＝有向グラフ上での閉路であることになかなか気づきませんでした。)
そこにもう1つ重なるサイクルを作ろうとすると、少なくともどこかの頂点が頑張って2つの出力辺を持つしかないのでありえないと分かります。

すると、サイクルでない部分では全ての要望を通し、サイクルの中では一番我慢強い人に我慢させる、という貪欲が成功します。

コード

深さ優先探索(DFS)で実装しました。

上で書いたようにサイクルの頂点たちから出力辺が出ることはないので、サイクルとそうでない部分をつなぐ辺は、サイクルに向かう辺だけです。
そこで有向グラフの辺の向きを全部ひっくり返してみます。
すると、逆にサイクルに進入する辺はなくなります。
おかげで、適当な頂点からDFSをしたとき、DFSをはじめた頂点に戻ってきたときに通ってきた頂点たちだけが、ちょうどサイクルとなることが保障されます。
後は通ってきた頂点の中で一番我慢強いやつの情報を持たせておけば、貪欲が簡単に実装できます。

using namespace std;

#define int long long

vector<int> e[100000];
int N, A[100000], B[100000], C[100000], D[100000];
int ans;
bool isUsed[100000];

void DFS(int v, int mi, int cnt, int s)
{
    if (v == s && (cnt & 1)) ans -= mi;
    if (isUsed[v]) return;
    isUsed[v] = true;
    for (int i = 0; i < e[v].size(); i++)
    {
        ans += B[e[v][i]] * max(C[v], D[v]);
        DFS(e[v][i], min(mi, B[e[v][i]] * abs(C[v] - D[v])), cnt + (D[v] > C[v]), s);
    }
}

signed main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        A[i]--;
        e[A[i]].push_back(i);
    }
    for (int i = 0; i < N; i++)
    {
        DFS(i, LLONG_MAX / 2, 0, i);
    }
    printf("%lld\n", ans);
    return 0;
}

4bitにっき

ぽよ

JOI2013春合宿Day4 プレゼント(Presents)

問題

解法

コード