【今日の精進】ARC099E - Indenpence

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

問題リンク

atcoder.jp

問題概要

頂点のグラフがあるよ。

いくつか辺を取り除いて2つ以下の完全グラフを作るとき、残す辺の本数の最小値を求めてね。

解法

補グラフについて考えると見通しが良くなります。

こうすると、辺でつながった部分を同じグループに属させないように二つに分ける問題となります。

これは典型的で、二部グラフかを判定すればよいです。

頂点数は、各連結成分ごとに白と黒の頂点数を求め、DPすればよいです。

提出コード

from collections import deque

N,M=map(int,input().split())
dist=[[0]*N for i in range(N)]
for i in range(M):
    A,B=map(int,input().split())
    dist[A-1][B-1]=1
    dist[B-1][A-1]=1
gr=[set() for i in range(N)]
for i in range(N):
    for j in range(i+1,N):
        if dist[i][j]==0:
            gr[i].add(j)
            gr[j].add(i)
dp=[0]*(N*2)
dp[0]=1
now=[-1]*N
for i in range(N):
    wb=[1,0]
    if now[i]==-1:
        now[i]=0
        vert=deque([i])
        while len(vert)>0:
            pos=vert.pop()
            for i in gr[pos]:
                if now[i]!=-1 and now[i]!=1-now[pos]:
                    print(-1)
                    exit()
                if now[i]==-1:
                    now[i]=1-now[pos]
                    wb[now[i]]+=1
                    vert.append(i)
        for i in range(N,-1,-1):
            if dp[i]==1:
                dp[i]=0
                dp[i+wb[0]]=1
                dp[i+wb[1]]=1
ans=N*N
for i in range(N+1):
    if dp[i]==1:
        ans=min(ans,i*(i-1)//2+(N-i)*(N-i-1)//2)
print(ans)

atcoder.jp

感想

視点を変えるのって難しいよね