Submission #2229290


Source Code Expand

#http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2435165
#AOJ最大流プログラム
#FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

import collections
class Dinic:

    def __init__(self, n):
        self.n = n
        self.g = [[] for i in range(n)]

    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr])-1])

    def add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])

    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level

    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in range(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

#FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO


#今回の問題分(インプット、頂点の組)FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

n, m, pp, gg=[int(i) for i in input().split()]
if gg!=0:
    ll=[int(i) for i in input().split()]
uvc=[]
for i in range(n):
    uvc.append([int(i) for i in input().split()])



#FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

#頂点の組u,vと辺の重みcからグラフ作って最大流で解くFOOOOOOOOOOOOOOOOOOOOOOO

V=m+10 #(s追加 ついでになんか追加)
dinic = Dinic(V)

try: 
for i in range(gg): #魔法石から魔法使いへの辺
    u, v, c = V-1, ll[i], 10**8
    dinic.add_edge(u, v, c)
except: print(123)
               
for i in range(n): #魔法使いから魔法使いへの辺
    u, v, c = uvc[i][0],uvc[i][1],uvc[i][2]      
    dinic.add_edge(u, v, c)


if dinic.max_flow(V-1, 0)>=pp:
    print("Yes")
else:
    print("No")


#FOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

Submission Info

Submission Time
Task H - お風呂は気持ちいい
User Yuki_Utaai
Language Python (3.4.3)
Score 0
Code Size 2951 Byte
Status RE
Exec Time 17 ms
Memory 3192 KB

Judge Result

Set Name f1t basic
Score / Max Score 0 / 40 0 / 100
Status
RE × 13
RE × 14
Set Name Test Cases
f1t f1t/basic_case00, f1t/basic_case01, f1t/basic_case02, f1t/basic_case03, f1t/basic_case04, f1t/basic_case05, f1t/basic_case06, f1t/basic_case07, f1t/basic_case08, f1t/basic_case09, f1t/sample00, f1t/sample01, f1t/sample02
basic basic/basic_case00, basic/basic_case01, basic/basic_case02, basic/basic_case03, basic/basic_case04, basic/basic_case05, basic/basic_case06, basic/basic_case07, basic/basic_case08, basic/basic_case09, basic/corner00, basic/sample00, basic/sample01, basic/sample02
Case Name Status Exec Time Memory
sample00 RE 17 ms 3192 KB
sample01 RE 17 ms 3192 KB
sample02 RE 17 ms 3192 KB
basic/basic_case00 RE 17 ms 3192 KB
basic/basic_case01 RE 17 ms 3192 KB
basic/basic_case02 RE 17 ms 3192 KB
basic/basic_case03 RE 17 ms 3192 KB
basic/basic_case04 RE 17 ms 3192 KB
basic/basic_case05 RE 17 ms 3192 KB
basic/basic_case06 RE 17 ms 3192 KB
basic/basic_case07 RE 17 ms 3192 KB
basic/basic_case08 RE 17 ms 3192 KB
basic/basic_case09 RE 17 ms 3192 KB
basic/corner00 RE 17 ms 3192 KB
basic/sample00 RE 17 ms 3192 KB
basic/sample01 RE 17 ms 3192 KB
basic/sample02 RE 17 ms 3192 KB
f1t/basic_case00 RE 17 ms 3192 KB
f1t/basic_case01 RE 17 ms 3192 KB
f1t/basic_case02 RE 17 ms 3192 KB
f1t/basic_case03 RE 17 ms 3192 KB
f1t/basic_case04 RE 17 ms 3192 KB
f1t/basic_case05 RE 17 ms 3192 KB
f1t/basic_case06 RE 17 ms 3192 KB
f1t/basic_case07 RE 17 ms 3192 KB
f1t/basic_case08 RE 17 ms 3192 KB
f1t/basic_case09 RE 17 ms 3192 KB
f1t/sample00 RE 17 ms 3192 KB
f1t/sample01 RE 17 ms 3192 KB
f1t/sample02 RE 17 ms 3192 KB