Submission #19430196


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)
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)
s = 2*m
t = s+1
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 0
Code Size 7958 Byte
Status RE
Exec Time 124 ms
Memory 71740 KB

Judge Result

Set Name All
Score / Max Score 0 / 7
Status
RE × 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 RE 124 ms 71284 KB
01 RE 110 ms 71344 KB
02 RE 111 ms 71692 KB
03 RE 111 ms 71496 KB
04 RE 108 ms 71492 KB
05 RE 111 ms 71624 KB
06 RE 111 ms 71552 KB
07 RE 113 ms 71552 KB
08 RE 107 ms 71564 KB
09 RE 110 ms 71456 KB
10 RE 108 ms 71404 KB
11 RE 108 ms 71400 KB
12 RE 115 ms 71740 KB
13 RE 115 ms 71704 KB
14 RE 117 ms 71432 KB
15 RE 113 ms 71444 KB
16 RE 114 ms 71560 KB
17 RE 114 ms 71516 KB
18 RE 116 ms 71444 KB
19 RE 116 ms 71600 KB
90 RE 97 ms 70320 KB
91 RE 95 ms 70192 KB