Contest Duration: - (local time) (300 minutes) Back to Home

Submission #19430215

Source Code Expand

Copy
```import sys

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:
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._inf = 10**12
#                 self._negE = self.add_edge(self._negt, self._negs, self._negf, -self._inf)
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):
for i in range(m):
for j in nns[i]:
for i in range(m):
res = g.flow(s,t,2)
print(-res[1])```

#### Submission Info

Submission Time 2021-01-14 20:54:49+0900 R - グラフ shotoyoo PyPy3 (7.3.0) 7 7958 Byte AC 358 ms 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