\nhttp:\/\/www.lydsy.com\/JudgeOnline\/problem.php?id=1565
\nhttps:\/\/www.byvoid.com\/blog\/noi-2009-pvz<\/p>\n
\u62d3\u6251\u6392\u5e8f \uff0b \u6700\u5927\u6743\u95ed\u5408\u5b50\u56fe\u3002<\/p>\n
\r\n\r\nconst int N = 600 + 3, M = N * N * 4;\r\n\r\n\r\nstruct Network_Flow{\r\n \r\n int D[N], hd[N], suc[M], to[M], cap[M];\r\n int n, m, s, t;\r\n \r\n inline void ae(int x, int y, int c){\r\n suc[m] = hd[x], hd[x] = m, to[m] = y, cap[m++] = c,\r\n suc[m] = hd[y], hd[y] = m, to[m] = x, cap[m++] = 0;\r\n }\r\n \r\n inline void aee(int x, int y, int c){\r\n suc[m] = hd[x], hd[x] = m, to[m] = y, cap[m++] = c,\r\n suc[m] = hd[y], hd[y] = m, to[m] = x, cap[m++] = c;\r\n }\r\n \r\n#define v to[i]\r\n#define c cap[i]\r\n#define f cap[i^1]\r\n \r\n LL sap(){\r\n LL z=0; static int cnt[N],cur[N],pre[N];\r\n fill(D,D+n,n),fill(cnt,cnt+n,0);cnt[n]=n;\r\n int u=s;cur[s]=hd[s];while (D[s]){\r\n#define i cur[u]\r\n if (u==t){\r\n int d=INF;for(u=s;u!=t;u=v)checkMin(d,c);\r\n z+=d;for(u=s;u!=t;u=v)f+=d,c-=d;u=s;\r\n }\r\n#undef i\r\n int i;for(i=cur[u];i;i=suc[i]){\r\n if(D[u]+1==D[v]&&c){cur[u]=i,cur[v]=hd[v],pre[v]=u,u=v;break;}\r\n }\r\n if (!i){\r\n if (!--cnt[D[u]])break;\r\n D[u]=1;REP_G(i,u)if(c)checkMax(D[u],D[v]);--D[u];\r\n ++cnt[D[u]];if(u==s)cur[u]=hd[u];else u=pre[u];\r\n }\r\n }\r\n \r\n return z;\r\n }\r\n \r\n void init(int _n){\r\n n = _n; s = 0, t = n + 1; m = 2; n = t + 1;\r\n fill(hd, hd+n, 0);\r\n }\r\n \r\n} G;\r\n#undef v\r\n#undef c\r\n#undef f\r\n\r\n\r\nVI _adj[N], adj[N]; int inD[N], scr[N], h[N], q[N] = {M}, op, cz, u, v;\r\nint r, c, s, t, n, m, ans;\r\n\r\ninline void add_edge(int x, int y){\r\n ++inD[y], _adj[x].PB(y);\r\n}\r\n\r\ninline int id(int x, int y){\r\n return x * c + y + 1;\r\n}\r\n\r\n\r\n\r\n#define v _adj[u][i]\r\nvoid init(){\r\n RD(r, c);\r\n \r\n REP(i, r) REP(j, c){\r\n if (j != 0) add_edge(id(i, j), id(i, j-1));\r\n int t, x, y; RDD(scr[id(i, j)]);\r\n Rush RD(x, y), add_edge(id(i, j), id(x, y));\r\n }\r\n \r\n n = r * c;\r\n \r\n \/\/ Toposort ..\r\n \r\n op = 0;\r\n REP_1(i, n) if (!inD[i])\r\n q[++op] = i;\r\n \r\n while (op){\r\n u = q[op--];\r\n REP(i, SZ(_adj[u])){\r\n --inD[v];\r\n if (!inD[v])\r\n q[++op] = v;\r\n }\r\n }\r\n \r\n \/\/ Graph Initializing..\r\n \r\n \r\n G.init(n);\r\n \r\n REP_1(u, n) if (!inD[u]){\r\n \r\n if (scr[u] > 0){\r\n G.ae(G.s, u, scr[u]);\r\n ans += scr[u];\r\n }\r\n else\r\n G.ae(u, G.t, -scr[u]);\r\n \r\n REP(i, SZ(_adj[u])){\r\n if (!inD[v]) G.ae(v, u, INF);\r\n }\r\n }\r\n \r\n}\r\n#undef v\r\n\r\n\r\n\r\nint main(){\r\n \r\n#ifndef ONLINE_JUDGE\r\n freopen("\/users\/xiaodao\/desktop\/Exercise\/in.txt", "r", stdin);\r\n \/\/freopen("\/users\/xiaodao\/desktop\/Exercise\/out.txt", "w", stdout);\r\n#endif\r\n \r\n init();\r\n printf("%d\\n", ans - G.sap());\r\n}\r\n\r\n\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[22],"tags":[],"class_list":["post-1179","post","type-post","status-publish","format-standard","hentry","category-bzoj"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-j1","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1179","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1179"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1179\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1179"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1179"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1179"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}