【BZOJ1001】【BJOI2006】狼抓兔子

这道题本来G10跟我说是网络流的

然后我就直接写了个Dinic

于是

1

于是去搜了一下题解

发现是什么对偶图最短路。。对偶图最短路=最小割=最大流

因为这个图结构固定所以构造对偶图很简单

无标题

大概就是。。原来的每一块变成一个点,原来的边对应新图中的边

然后跑Dijkstra就完了

2(虽然比别人写的还是慢点)

说点什么

您将是第一位评论人!

提醒
wpDiscuz