コンテンツにスキップ

主客転倒

タグ「主客転倒」の記事 1 件

牛客小白月赛138 D - Light up the Graph

頂点 nn 個、辺 mm 本の単純無向グラフがあります。各頂点は白か黒で塗られています(文字列 ss の ii 文字目が 0 なら白、1 なら黒)。

好きな頂点の集合を点灯させます(何も点灯させなくてもよい)。各頂点について、隣接する点灯した頂点の個数をその頂点の「値」とします。白い頂点の値の総和から黒い頂点の値の総和を引いたものを最大化する点灯のしかたを 1 つ出力してください(n,mn, m の総和はそれぞれ ≤2×105\le 2 \times 10^5)。

頂点 vv を点灯させるとき cv=1c_v = 1、させないとき cv=0c_v = 0 とします。uu が白なら wu=1w_u = 1、黒なら wu=−1w_u = -1 とおくと、最大化したい値は

∑uwu∑v∈N(u)cv\sum_{u} w_u \sum_{v \in N(u)} c_v

です(N(u)N(u) は uu に隣接する頂点の集合)。

この式は「白い頂点 uu から見て、隣の何個が点灯しているか」を数えています。これを「点灯した頂点 vv から見て、隣に白と黒が何個ずつあるか」に数え直します。辺 (u,v)(u, v) ごとに足しているだけなので、和の順番を入れ替えて

∑vcv∑u∈N(v)wu\sum_{v} c_v \sum_{u \in N(v)} w_u

と書けます。tv=∑u∈N(v)wut_v = \sum_{u \in N(v)} w_u(vv に隣接する白い頂点の個数から、黒い頂点の個数を引いたもの)とおくと、値は ∑vcvtv\sum_v c_v t_v です。

tvt_v は cc によらない定数なので、各頂点の cvc_v は独立に決められます。tv>0t_v > 0 なら点灯させ、tv<0t_v < 0 なら点灯させなければ最大になります。tv=0t_v = 0 の頂点は、どちらにしても値は変わりません。

点灯させた頂点の色は関係ないことに注意してください。値に効くのは隣の頂点の色だけです。

tvt_v は各頂点の隣接リストを一度ずつ見れば求まるので、計算量は O(n+m)O(n + m) です。

1 つ目のサンプルの頂点 1 は、隣が頂点 4(白)と頂点 5(黒)なので t1=0t_1 = 0 です。そのため、サンプル出力では点灯させていますが、点灯させなくても最大値 44 は変わりません。

Python
for _ in range(int(input())):
N,M=map(int,input().split())
S=input()
g=[[]for i in range(N)]
for _ in range(M):
u,v=map(int,input().split())
u,v=u-1,v-1
g[u].append(v)
g[v].append(u)
ans = []
for u in range(N):
t = 0
for v in g[u]:
if S[v] == "0":
t += 1
else:
t -= 1
if t > 0:
ans.append(u+1)
print(len(ans))
print(*ans)

各頂点 u について、隣接する白い頂点を +1+1、黒い頂点を −1-1 として足した t を求め、正なら点灯させています。点灯させる頂点が 00 個のときは print(*ans) が空行を出力するので、問題の出力形式どおりになります。