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
16
2017-07
2017-07
![UVALive 7427 Elementary Math (二分匹配)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
UVALive 7427 Elementary Math (二分匹配)
题意:~
思路:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PI;
const int MAXN = 10010;
const int MAXM = 10010;
struct...
07月16日
3,131
16
2017-07
2017-07
![UVALive 7425 Cleaning Pipes (2-sat)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
UVALive 7425 Cleaning Pipes (2-sat)
题意:~
思路:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PI;
const int MAXN = 10020;
const int MAXM = 5000010;
stru...
07月16日
3,949
07
2017-07
2017-07
![Floyd求最小环](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
Floyd求最小环
算法引入:
*求一个图G中的最小环路的朴素算法为:每次找到一条边,删除了求这两点之间的最短路径;
*若能求出,则这条最短路径与原来的边构成一个环,不过时间复杂度略高;
*算法思想;
*Floyd算法是按照顶点的编号增加的顺序更新最短路径的;
*如果存在最小环,则会在这个环中的点编号最大的那个点u更新最短路径之前发现这个环;
*即当点u被拿来更新i到j的最短路...
07月07日
3,126
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
25
2017-03
2017-03
![Codeforces 131D Subway (缩点)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
Codeforces 131D Subway (缩点)
题意:~
思路:缩点之后求个最短路
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PI;
typedef pair< P...
03月25日
1,942
17
2017-03
2017-03
![Codeforces 96D Volleyball (shortest paths)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
Codeforces 96D Volleyball (shortest paths)
题意:~
思路:先处理出乘坐出租车能到达的点,建图跑最短路即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 100010;
const LL INF = 1e18 + 7;
const int lowINF...
03月17日
1,752
17
2017-02
2017-02
![UVALive 6129 Sofa, So Good (KM)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
UVALive 6129 Sofa, So Good (KM)
题意:~
思路:最小权匹配,跑两遍KM,第二次建边要处理每个工人第一次做工的时间差。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int>...
02月17日
2,673
14
2017-02
2017-02
![HDU 5934 Bomb (Tarjan)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 5934 Bomb (Tarjan)
题意:~
思路:如果v能引爆u那么v向u建边。之后用Tarjin强连通缩点,变成有向无环图,将那些入度为0的点的集合求最小引爆带价。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typ...
02月14日
2,391
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