結果

問題 No.3024 全単射的
コンテスト
ユーザー Vincent Shaw
提出日時 2025-02-14 21:40:42
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,277 ms / 5,000 ms
コード長 2,582 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 539 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 81,792 KB
最終ジャッジ日時 2025-02-14 21:40:52
合計ジャッジ時間 8,170 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import deque

def hopcroft_karp(graph, N, nR):
    # graph: list of lists, graph[u] = list of neighbor indices (right side) for left vertex u
    # N: 左側頂点数, nR: 右側頂点数
    INF = 10**9
    dist = [0] * N
    pairU = [-1] * N      # 左側各頂点に対するマッチ相手（右側頂点のインデックス）　-1:未マッチ
    pairV = [-1] * nR     # 右側各頂点に対するマッチ相手（左側頂点のインデックス）　-1:未マッチ

    def bfs():
        q = deque()
        for u in range(N):
            if pairU[u] == -1:
                dist[u] = 0
                q.append(u)
            else:
                dist[u] = INF
        dist_nil = INF
        while q:
            u = q.popleft()
            if dist[u] < dist_nil:
                for v in graph[u]:
                    if pairV[v] == -1:
                        dist_nil = dist[u] + 1
                    else:
                        if dist[pairV[v]] == INF:
                            dist[pairV[v]] = dist[u] + 1
                            q.append(pairV[v])
        return dist_nil != INF

    def dfs(u):
        for v in graph[u]:
            # vが未マッチなら，またはマッチしている相手を先にdfsして増補パスが見つかれば
            if pairV[v] == -1 or (dist[pairV[v]] == dist[u] + 1 and dfs(pairV[v])):
                pairU[u] = v
                pairV[v] = u
                return True
        dist[u] = INF
        return False

    matching = 0
    while bfs():
        for u in range(N):
            if pairU[u] == -1:
                if dfs(u):
                    matching += 1
    return matching

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    # 入力はバイト列なので整数に変換
    it = map(int, data)
    N = next(it)
    M = next(it)  # 実際は使いません。景品番号の上限
    bots = []
    prizes_set = set()
    for _ in range(N):
        X = next(it)
        Y = next(it)
        bots.append((X, Y))
        prizes_set.add(X)
        prizes_set.add(Y)
    # 座標圧縮
    prizes_list = sorted(prizes_set)
    comp = {p: i for i, p in enumerate(prizes_list)}
    nR = len(prizes_list)

    # 左側頂点 i (0-indexed) の隣接リストを作成
    graph = [[] for _ in range(N)]
    for i, (X, Y) in enumerate(bots):
        graph[i].append(comp[X])
        graph[i].append(comp[Y])
    
    ans = hopcroft_karp(graph, N, nR)
    sys.stdout.write(str(ans) + "\n")

if __name__ == '__main__':
    main()
0