# Difference between revisions of "2018 ICPC Mid-Central Regional"

Jump to navigation
Jump to search

Xiejiadong (talk | contribs) (Created page with "== Problem A == Solved by Kilo_5723. 00:56:00 (+) == Problem B == Solved by Xiejiadong. 00:03:24 (+) == Problem C == Solved by Weaver_zhu. 02:42:52 (+) == Problem D ==...") |
|||

Line 10: | Line 10: | ||

Solved by Weaver_zhu. 02:42:52 (+) | Solved by Weaver_zhu. 02:42:52 (+) | ||

+ | |||

+ | 题意：maze mxn 大小，每个格子可以花费一定代价堵住，求花费最小的代价能然某个点走不到边界。 | ||

+ | |||

+ | 题解：裸的最小割，拆点入点到出点中间边连一条容量为花费的边。不能放障碍变容量就是 inf，其余出点连到上下左右四个格子的入点。根据最小割的定义就是去掉容量和最小的边使得图不联通，跑个最大流就行了 | ||

== Problem D == | == Problem D == |

## Revision as of 04:36, 7 October 2019

## Problem A

Solved by Kilo_5723. 00:56:00 (+)

## Problem B

Solved by Xiejiadong. 00:03:24 (+)

## Problem C

Solved by Weaver_zhu. 02:42:52 (+)

题意：maze mxn 大小，每个格子可以花费一定代价堵住，求花费最小的代价能然某个点走不到边界。

题解：裸的最小割，拆点入点到出点中间边连一条容量为花费的边。不能放障碍变容量就是 inf，其余出点连到上下左右四个格子的入点。根据最小割的定义就是去掉容量和最小的边使得图不联通，跑个最大流就行了

## Problem D

Solved by Xiejiadong. 00:22:46 (+)

## Problem E

Solved by Weaver_zhu. 00:16:54 (+)

## Problem F

Solved by Xiejiadong. 00:29:33 (+)

## Problem G

Solved by Xiejiadong. 01:33:13 (+)

## Problem H

Solved by Xiejiadong. 00:20:27 (+)

## Problem I

Unsolved.

## Problem J

Solved by Kilo_5723. 02:47:25 (+3)

## Problem K

Solved by Weaver_zhu. 01:07:32 (+)