23
2017-07
2017-07
![UVALive 4957 Fake scoreboard (最大流)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
UVALive 4957 Fake scoreboard (最大流)
题意:~
思路:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PI;
const int INF = 0x3f3f3f3f;
const int MAXN = 1500;
const...
07月23日
3,913
04
2017-04
2017-04
![UVALive 7122 Tight Knight (最小割)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
UVALive 7122 Tight Knight (最小割)
题意:~
思路:给定一个图,几个障碍点,问删除至多一条边能否使得起始位置到不了终点位置,即求最小割。数据范围较大,还卡SAP,ISAP,只能用dinic过?
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long lo...
04月04日
1,834
14
2017-02
2017-02
![HDU 5988 Coding Contest (费用流)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 5988 Coding Contest (费用流)
题意:在n个点上有着食物,有m条边,除了第一个走的人,其他人都有pi的概率这条边,再大家都能获得食物的前提下,求破坏网络的概率最小。
思路:
每条边有走的次数(流量),每条边走一次发生破坏概率为p(流量1,费用p),容易想到费用流。可是费用流往往是费用相加的,这个是概率,只能相乘。有什么办法,log函数可以把乘除法转换为加减法。所以对每个概率取个log当成费...
02月14日
2,234
03
2016-10
2016-10
![HDU 3251 Being a Hero (最小割)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 3251 Being a Hero (最小割)
题目链接:点我~~
题意:n个点m条边的有向图,f个可选城市,每个城市都有其价值w,国王的城市在1,要分配一些城市,分配的原则是:只能在规定的f个城市中选若干个,这f个城市每个都有一个价值,被选择的城市要与城市1隔离,所以需要花费一些费用来破坏边。问能获取到的最大利益,以及要破坏的边。
思路:求能获取的最大利益,先建立一个超级汇点,将f个可选城市与汇点连接,...
10月03日
1,863
23
2016-09
2016-09
![HDU 5889 Barricade (最短路+最小割)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 5889 Barricade (最短路+最小割)
题目链接:点我~~
题意:1000个点10000条边的无向图,敌人从n走一条最短路到1,在第i条路设置障碍的代价是wi,求最少的代价使得敌人至少会遇到一次障碍。
思路:先确定最短路,然后在最短路径上跑一个网络流,即可求出最小割。
#include <bits/stdc++.h>
using namespace std;
typedef lon...
09月23日
1,933
20
2016-07
2016-07
![HDU 5294 Tricks Device (最短路+网络流)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 5294 Tricks Device (最短路+网络流)
题意:n个点,m条边,构建有权无向图。求出删去最少条边数没有最短路,以及删出最多条边,使最短路的长度不变。
思路:先处理出最短路,然后使用结果的dis数组,若dis[v]-dis[u] = w(u,v),则该路就是最短路经中的一条边。建出最短路径之后跑最大流,流量是有多少边权相同的重边,跑出来就是最小割,也就是阻断所有最短路的最小花费。最后再跑最短路,边权为...
07月20日
2,487