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
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
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-09
2016-09
![HDU 3499 Flight (分层图最短路)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
HDU 3499 Flight (分层图最短路)
题目链接:点我~~
题意:在N个点,M条带权边的图上,查询从点S到点E的最短路径,并且有一次机会可以把一条边的权值变成原来的二分之一。
思路:利用分层图的思想建图,
u->v需要建立,addedge(u+n,v+n),addedge(u,v+n,w/2),表示分两层,当从上层到下层,即使用了题中所给的条件。
#include <bits/stdc...
09月20日
2,611
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
31
2016-01
2016-01
![ZOJ 2750 Idiomatic Phrases Game(最短路)](http://www.carlstedt.cn/wp-content/themes/Carlstedt/images/ajaxloader.gif)
ZOJ 2750 Idiomatic Phrases Game(最短路)
将每个字符串的前后四位取出,如果A串的后面四位跟B串的前面四位相等,说明A可以通往B,然后以此建图,直接跑最短路就可以了
#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm&g...
01月31日
2,230