Submission #19430215


Source Code Expand

Copy
import sys
input = lambda : sys.stdin.readline().rstrip()

sys.setrecursionlimit(2*10**5+10)
write = lambda x: sys.stdout.write(x+"\n")
_print = lambda *x: print(*x, file=sys.stderr)

n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
ns = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if g[i][j]:
            ns[i].append(j)
def scc(ns):
    n = len(ns)
    l = []
    vmin = [n]*n
    vnum = [-1]*n
    val = 0
    wait = []
    waiting = [False]*n
    seen = [[] for _ in range(n)]
    unseen = [[] for _ in range(n)]
    for u in range(n):
        if vnum[u]!=-1:
            continue
        q = [u]
        while q:
            u = q.pop()
            if u<0:
                u = ~u
                mm = vmin[u]
                for v in seen[u]:
                    mm = min(mm, vmin[v])
                for v in unseen[u]:
                    mm = min(mm, vnum[v])
                vmin[u] = mm
                if mm==vnum[u]:
                    ll = []
                    while True:
                        v = wait.pop()
                        waiting[v] = False
                        ll.append(v)
                        if u==v:
                            break
                    l.append(ll)
            elif vnum[u]!=-1:
                continue
            else:
                q.append(~u)
                wait.append(u)
                waiting[u] = True
                vnum[u] = vmin[u] = val
                val += 1
                for v in ns[u]:
                    if vnum[v]==-1:
                        q.append(v)
                        seen[u].append(v)
                    elif waiting[v]:
                        unseen[u].append(v)
    return l
l = scc(ns)
m = len(l)
nns = [set() for _ in range(m)]
cs = [None]*n
vs = [0]*m
for i in range(m):
    vs[i] = len(l[i])
    for u in l[i]:
        cs[u] = i
for u in range(n):
    ui = cs[u]
    for v in ns[u]:
        vi = cs[v]
        if ui!=vi:
            nns[ui].add(vi)
from typing import NamedTuple, Optional, List, Tuple, cast
from heapq import heappush, heappop

# mincostflow
class MCFGraph:
    class Edge(NamedTuple):
        src: int
        dst: int
        cap: int
        flow: int
        cost: int

    class _Edge:
        def __init__(self, dst: int, cap: int, cost: int) -> None:
            self.dst = dst
            self.cap = cap
            self.cost = cost
            self.rev: Optional[MCFGraph._Edge] = None

    def __init__(self, n: int, neg=False, negf=None) -> None:
        self._neg = neg
        if neg:
            n += 2
            self._negs = n-2
            self._negt = n-1
            self._negf = negf
            self._negfsum = 0
            self._negcsum = 0
            self._negdone = False            
        self._n = n
        self._g: List[List[MCFGraph._Edge]] = [[] for _ in range(n)]
        self._edges: List[MCFGraph._Edge] = []    

    def add_edge(self, src: int, dst: int, cap: int, cost: int) -> int:
        assert 0 <= src < self._n
        assert 0 <= dst < self._n
        assert 0 <= cap
        if cost<0 and self._neg:
            if not self._negdone:
                global s,t
                self._negdone = True
                self.add_edge(self._negs, s, self._negf, 0)
                self.add_edge(t, self._negt, self._negf, 0)
                # 後で指定した流量を流すための処理
#                 self._inf = 10**12
#                 self._negE = self.add_edge(self._negt, self._negs, self._negf, -self._inf)
            self.add_edge(self._negs, dst, cap, 0)
            self.add_edge(src, self._negt, cap, 0)
            self.add_edge(dst, src, cap, -cost)
            self._negfsum += cap
            self._negcsum += cap*cost
        else:
            m = len(self._edges)
            e = MCFGraph._Edge(dst, cap, cost)
            re = MCFGraph._Edge(src, 0, -cost)
            e.rev = re
            re.rev = e
            self._g[src].append(e)
            self._g[dst].append(re)
            self._edges.append(e)
            return m

    def get_edge(self, i: int) -> Edge:
        assert 0 <= i < len(self._edges)
        e = self._edges[i]
        re = cast(MCFGraph._Edge, e.rev)
        return MCFGraph.Edge(
            re.dst,
            e.dst,
            e.cap + re.cap,
            re.cap,
            e.cost
        )

    def edges(self) -> List[Edge]:
        return [self.get_edge(i) for i in range(len(self._edges))]

    def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> Tuple[int, int]:
        if self._neg:
            flow_limit += self._negfsum
            val = self.slope(self._negs, self._negt, flow_limit)[-1]
            return (val[0], val[1] + self._negcsum)
        else:
            return self.slope(s, t, flow_limit)[-1]

    def slope(self, s: int, t: int, flow_limit: Optional[int] = None) -> List[Tuple[int, int]]:
        assert 0 <= s < self._n
        assert 0 <= t < self._n
        assert s != t
        if flow_limit is None:
            flow_limit = cast(int, sum(e.cap for e in self._g[s]))

        dual = [0] * self._n
        prev: List[Optional[Tuple[int, MCFGraph._Edge]]] = [None] * self._n

        def refine_dual() -> bool:
            pq = [self.enc(0, s)]
            visited = [False] * self._n
            dist: List[Optional[int]] = [None] * self._n
            dist[s] = 0
            while pq:
                dist_v, v = self.dec(heappop(pq))
                if visited[v]:
                    continue
                visited[v] = True
                if v == t:
                    break
                dual_v = dual[v]
                for e in self._g[v]:
                    w = e.dst
                    if visited[w] or e.cap == 0:
                        continue
                    reduced_cost = e.cost - dual[w] + dual_v
                    new_dist = dist_v + reduced_cost
                    dist_w = dist[w]
                    if dist_w is None or new_dist < dist_w:
                        dist[w] = new_dist
                        prev[w] = v, e
                        heappush(pq, self.enc(new_dist, w))
            else:
                return False
            dist_t = dist[t]
            for v in range(self._n):
                if visited[v]:
                    dual[v] -= cast(int, dist_t) - cast(int, dist[v])
            return True

        flow = 0
        cost = 0
        prev_cost_per_flow: Optional[int] = None
        result = [(flow, cost)]
        while flow < flow_limit:
            if not refine_dual():
                break
            f = flow_limit - flow
            v = t
            while prev[v] is not None:
                u, e = cast(Tuple[int, MCFGraph._Edge], prev[v])
                f = min(f, e.cap)
                v = u
            v = t
            while prev[v] is not None:
                u, e = cast(Tuple[int, MCFGraph._Edge], prev[v])
                e.cap -= f
                assert e.rev is not None
                e.rev.cap += f
                v = u
            c = -dual[s]
            flow += f
            cost += f * c
            if c == prev_cost_per_flow:
                result.pop()
            result.append((flow, cost))
            prev_cost_per_flow = c
        return result
    def enc(self,d,v):
        return d*(self._n)+v
    def dec(self,val):
        return divmod(val,self._n)
# nns: DAG
g = MCFGraph(2*m+2, neg=True, negf=2)
s = 2*m
t = s+1
for i in range(m):
    g.add_edge(i,i+m,1,-vs[i])
    g.add_edge(i,i+m,1,0)
for i in range(m):
    for j in nns[i]:
        g.add_edge(i+m,j,2,0)
for i in range(m):
    g.add_edge(s,i,2,0)
    g.add_edge(i+m,t,2,0)
res = g.flow(s,t,2)
print(-res[1])

Submission Info

Submission Time
Task R - グラフ
User shotoyoo
Language PyPy3 (7.3.0)
Score 7
Code Size 7958 Byte
Status AC
Exec Time 358 ms
Memory 77948 KB

Judge Result

Set Name All
Score / Max Score 7 / 7
Status
AC × 22
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 90, 91
Case Name Status Exec Time Memory
00 AC 273 ms 74420 KB
01 AC 285 ms 75016 KB
02 AC 288 ms 76524 KB
03 AC 299 ms 77372 KB
04 AC 240 ms 73708 KB
05 AC 202 ms 73996 KB
06 AC 169 ms 73472 KB
07 AC 157 ms 73076 KB
08 AC 170 ms 73436 KB
09 AC 141 ms 72568 KB
10 AC 273 ms 75972 KB
11 AC 291 ms 76388 KB
12 AC 306 ms 76340 KB
13 AC 318 ms 77684 KB
14 AC 330 ms 77948 KB
15 AC 355 ms 77572 KB
16 AC 349 ms 76916 KB
17 AC 349 ms 77256 KB
18 AC 358 ms 77772 KB
19 AC 358 ms 76592 KB
90 AC 94 ms 70152 KB
91 AC 96 ms 69960 KB