【今日の精進】ABC241G - Round Robin

毎日格上の問題を倒すやつの14日目です。¹

問題リンク

atcoder.jp

問題概要

人でリーグ戦をするよ。

すでに何戦かは終わらせてるから、このあと単独優勝する可能性がある人を列挙してね。

解法

が小さいため、多項式時間なら割と何でも間に合います。

なので、ひとりひとり判定するのを全員分行います。

判定したい人の分は、とりあえず残りを勝たせて良いです。

その時、ほかの人の勝利数を判定したい人未満にしなければいけません。

これの判定は、うまくグラフを作ることで行うことができます。いつものフローです。²

発想的には、片方だけ勝たせるのを全部のペアに対して行う感じです。

提出コード

from atcoder.maxflow import MFGraph
N,M=map(int,input().split())
win=[0 for i in range(N)]
lose=[0 for i in range(N)]
end=[[True for i in range(N)] for i in range(N)]
for i in range(M):
    W,L=map(int,input().split())
    win[W-1]+=1
    lose[L-1]+=1
    end[min(W-1,L-1)][max(W-1,L-1)]=False
ans=[]
for i in range(N):
    gr=MFGraph(N+N*N)
    cnt=1
    for j in range(N):
        if j==i:
            continue
        if N-2-lose[i]-win[j]<0:
            cnt=0
            break
        gr.add_edge(0,j+2,N-2-lose[i]-win[j])
        for k in range(j+1,N):
            if end[j][k] and not(k==i):
                cnt+=1
                gr.add_edge(j+2,N+cnt,1)
                gr.add_edge(k+2,N+cnt,1)
                gr.add_edge(N+cnt,1,1)
    if gr.flow(0,1)==cnt-1:
        ans.append(i+1)
print(*ans)

Submission #46200274 - AtCoder Beginner Contest 241（Sponsored by Panasonic）

感想

フローへの信頼が厚い

---

1. まさか半月続くとは…↩
2. 久しぶりな気がするけど↩