SRM632D1Med CandyCupRunningCompetition
これ， 400 ptぐらいだと思う
問題概要(原文)
$N$ 頂点 $M$ 本の無向辺からなる無向グラフが与えられる． $i$ 番の辺の容量は $3^i$ である． $0 \rightarrow N-1$ への最大フローを $10^9+7$ で割ったあまりを求めよ．
考察
容量がクソでかいので最大流を実際に流すのは難しい．
ここで，辺の容量が全て異なることに着目しよう．あるフローが $3^k$ 流れたとする．このとき，容量 $3^k$ の辺の容量は $0$ になるが，他の辺の容量はまだまだ大きい．
よって以下のようにすればよい．
- 最大フローが $3^i$ となるようなフローがあるか $M-1$ から $0$ に向かって探す
- 流せるかどうかは未使用の辺で容量が $3^i$ 以上の辺だけをつかって $0$ から $N-1$ へ移動可能かどうかと等しい
- union-findでさっきの辺たちをつないで， $0$ と $N-1$ がつながっていたなら，流せると判定して， $i$ 番の辺に使用済みマークをつける．
計算量は $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 CandyCupRunningCompetition
{
public int findMaximum(int N, int[] A, int[] B)
{
const long MOD = (long)1e9 + 7;
var m = A.Length;
var powed = new long[m + 1];
powed[0] = 1;
for (int i = 1; i <= m; i++)
powed[i] = (powed[i - 1] * 3) % MOD;
long ans = 0;
var used = new bool[m];
for (int i = m - 1; i >= 0; i--)
{
var s = new DisjointSet(N);
for (int j = i; j < m; j++)
{
if (used[j]) continue;
s.Unite(A[j], B[j]);
}
if (s.IsUnited(0, N - 1))
{
ans = (ans + powed[i]) % MOD;
used[i] = true;
}
}
return (int)ans;
}
}
#region DisjointSet
public class DisjointSet
{
public int[] par, ranks, count;
public DisjointSet(int n)
{
par = new int[n];
count = new int[n];
for (int i = 0; i < n; i++)
{
par[i] = i;
count[i] = 1;
}
ranks = new int[n];
}
public int this[int id] { get { return (par[id] == id) ? id : this[par[id]]; } }
public bool Unite(int x, int y)
{
x = this[x]; y = this[y];
if (x == y) return false;
if (ranks[x] < ranks[y])
{
par[x] = y;
count[y] += count[x];
}
else
{
par[y] = x;
count[x] += count[y];
if (ranks[x] == ranks[y])
ranks[x]++;
}
return true;
}
public int Size(int x) { return count[this[x]]; }
public bool IsUnited(int x, int y) { return this[x] == this[y]; }
}
#endregion
コメント
- $10^9+7 \times 3$ はオーバーフローしうるので注意しよう(modを取るときはlongに限るなぁ)
