图论
欧拉, 汉密尔顿
欧拉回路
无向图
充要条件: 连通图, (0)或(2)个奇度数点
有向图
充要条件: 基图联通, 且
- 所有点出入度相同
- 或除起点终点外相同, 起点入度大(1), 终点入度小(1)
Fleury(弗罗莱)算法
void DFS(int u)
{
for (int i = 65; i <= 122; ++ i) // 'A' to 'z'
if (link[u][i])
{
link[u][i] = link[i][u] = false;
DFS(i);
}
rec[m --] = u;
}
解释:
- 每个点总有一个方向能走到终点
- 除了这个方向, 都会走回到自己
- 发现不论先走哪个方向, 把所有方向走完,都相当于走掉经过这点的环后走向终点, 然后记录这个点
Hierholzer's
中国邮递员模型
汉密尔顿
竞赛图
贝斯特best定理
连通性
Tarjana算法: 定义(dfn[u])为从根沿着树边走到这个点的时间戳, (low[u])为子树内的点沿着非树边最早能到达的时间戳(即(u ightarrow)(沿树边)子树中点(v ightarrow)(沿非树边)到某一点(low[u]))
这样定义的意义在于, 让走到这个点, 和从这个走回去, 是经过不同的边的, 从而形成环
强连通分量
Tarjan发现强连通分量是DFS搜索树的一棵子树, 而这个算法就是在这样的子树的根上找完这个强连通分量的
首先, 有向图的DFS搜索树有这几种边:
- 前向边: 写你妈
至于为什么儿子(v)已经访问过时, 要再判断是否在栈中:
如果不在栈中, 则儿子早已被访问过并被判定到一个SCC中, 那么他的dfn值很小, 用这个只更新后会导致自己SCC祖先的点也会变成这个值, 导致他low!=dfn.
由此再次明确: low为子树内最多能到达的祖先, 而非兄弟树
HDU4635 Strongly connected
给你一张有向简单图
问最多能加几条边, 使得仍然是简单图, 且整个图不强连通
Sol
(二周目)
(Fake)
我想到这个图到最后肯定是有两大块之间有桥(同一个方向), 互相不强连通, 而内部为了边数尽量多, 所以内部强连通
那么答案就是(n*(n-1)-m-x*(n - x)), 又因为和相等差小积大, 所以缩点后选一个最小的SCC作为那个(x)即可
(Right)
然而并没有这么简单, 万一原来连向这个(x)的边就有两种方向呢, 你让剩下的强连通, 这个也会被连进去
所以还要判一下SCC的出入度符合才行
BZOJ3887: USACO15JAN草鉴定Grass Cownoisseur
有一张(N(le 1e5))的有向图, 无边权点权, 求从(1)出发回到(1), 至多走一次逆向边, 最多能经过的节点数(一个点能重复经过)
Sol:
缩点之后, 将会是 一条反边 + 1 到这个边 + 这个边到1 这样一个环, 环的点权和最大
方法很多
- 那么需要得到 dis[1][u], dis[u][1], 第一个好求, 第二个相当于单汇最长路, 可以建反向边变成单源最长路
- 加入所有反边, 并标记, 直接跑最长路, 使他之多经过一条反边
- 建两层一样的图, 将上下层连边, 表示这条反向边, 则这层的1跑到那层的1即可
边双联通分量和桥
判断: 一条边(u ightarrow v), 假如(low[v]>dfn[u])则为割边
找边双在下面 BZOJ1718 中
POJ3694 Network <边双+并查集LCA>
给一个无向连通图, (N(le 10^5), M(le 2*10^5)), 然后有(Q(le 1000))次询问, 每次加一条边, 问当前桥的数量
Sol:
容易想到边双缩点后变成一棵树, 树边就是桥, 然后加一条边就会使这两点到(LCA)的路径全部缩成边双
然后就想到缩成树后维护一个并查集, 加边就把上述路径并起来
于是怎么实现呢? 不想写倍增LCA, 感觉可以直接跳, 然后有应为缩来缩去可能每个点的真实深度没有实时更新,然后求LCA时甚至不知道先跳哪个点, 怎么办?
(二周目)
方法很多, 先缩点
- 建出树, 一开始树边都是 (1), 然后树剖, 每次修改路径上边为 (0), 并查询总权值
- 用并查集, 每次修改从树上深的节点开始暴力条 fa , 然后并掉, 这样每个边并掉之后就不用走了, 复杂度优秀
struct Graph
{
int head[MAXN], nume; // cleared, -1 !!
struct Adj { int nex, to; } adj[MAXM << 1]; // 2x
void addedge(int from, int to)
{
adj[nume] = (Adj) { head[from], to };
head[from] = nume ++ ;
}
void link(int u, int v)
{
addedge(u, v);
addedge(v, u);
}
} g1, g2;
int idx, dfn[MAXN], low[MAXN]; // cleared
int stk[MAXN], top;
bool instk[MAXN];
int scc[MAXN], tot; // cleared
void Tarjan(int u, int fa)
{
dfn[u] = low[u] = ++ idx;
instk[stk[++ top] = u] = true;
for (int i = g1.head[u]; i != -1; i = g1.adj[i].nex)
{
if ((i ^ 1) == fa) continue;
int v = g1.adj[i].to;
if (!dfn[v])
{
Tarjan(v, i);
low[u] = min(low[u], low[v]);
}
else
{
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] > dfn[g1.adj[fa ^ 1].to])
{
++ tot;
while (true)
{
scc[stk[top]] = tot;
-- top;
if (stk[top + 1] == u) break;
}
}
}
int to[MAXN], dep[MAXN], fa[MAXN]; // cleared
int getf(int x)
{
if (fa[x] == x) return x;
else return fa[x] = getf(fa[x]);
}
void unite(int x, int y)
{
int fx = getf(x), fy = getf(y);
if (fx == fy) return;
fa[fx] = fy;
}
void DFS(int u)
{
dep[u] = dep[to[u]] + 1;
for (int i = g2.head[u]; i != -1; i = g2.adj[i].nex)
{
int v = g2.adj[i].to;
if (v == to[u]) continue;
// printf("%d ==> %d
", u, v);
to[v] = u;
++ ans;
DFS(v);
}
}
void solve(int x, int y)
{
x = getf(x), y = getf(y);
if (x == y) return ;
while (x != y)
{
if (dep[x] > dep[y]) swap(x, y);
unite(y, to[y]); -- ans;
y = getf(y);
}
}
void init()
{
ans = 0;
g1.nume = g2.nume = 0;
memset(g1.head, -1, sizeof g1.head);
memset(g2.head, -1, sizeof g2.head);
idx = 0; //
memset(dfn, 0, sizeof dfn); //
memset(low, 0, sizeof low); //
tot = 0; //
memset(scc, 0, sizeof scc); //
memset(fa, 0, sizeof fa); //
memset(to, 0, sizeof to); //
memset(dep, 0, sizeof dep); //
}
int main()
{
int T = 0, first = 1;
while (~scanf("%d%d", &n, &m) && n && m)
{
init();
for (int i = 1; i <= m; ++ i) // undirected
{
int u = in(), v = in();
g1.link(u, v);
}
for (int i = 1; i <= n; ++ i)
if (!dfn[i]) Tarjan(i, -1);
for (int u = 1; u <= n; ++ u)
{
for (int i = g1.head[u]; i != -1; i = g1.adj[i].nex)
{
if (scc[u] == scc[g1.adj[i].to]) continue;
g2.addedge(scc[u], scc[g1.adj[i].to]);
}
}
DFS(1);
for (int i = 1; i <= tot; ++ i) fa[i] = i;
q = in();
printf("Case %d:
", ++ T);
while (q --)
{
int x = in(), y = in();
x = scc[x], y = scc[y];
solve(x, y);
printf("%d
", ans);
}
puts("");
}
return 0;
}
BZOJ1718: [Usaco2006 Jan] Redundant Paths 分离的路径 <边双缩点板子>
题目要求: 边双缩点后, 问连几条边能使新图(树)中没有桥
Sol:
做过类似的题, BalticOI 2015 Nerwork, 连接按 DFS 序叶子的前一半和 + 一半长度后一半即可, 这样不会使得一棵子树叶子连边都在内部
所以答案就是 叶子/2 取上界
这题蓝题, 那题黑题... 然后各处的题解都是瞎几把乱讲, 没有具体说明
int dfn[MAXN], low[MAXN], idx;
bool cut[MAXM << 1];
void Tarjan(int u, int fa)
{
dfn[u] = low[u] = ++ idx;
for (int i = head[u]; i != -1; i = adj[i].nex)
{
int v = adj[i].to;
if ((i ^ 1) == fa) continue;
if (dfn[v])
{
low[u] = min(low[u], dfn[v]);
}
else
{
Tarjan(v, i);
low[u] = min(low[u], low[v]);
}
}
if (fa != -1 && low[u] > dfn[adj[fa ^ 1].to]) cut[fa] = cut[fa ^ 1] = true;
}
int bel[MAXN], cnt;
void DFS(int u, int fa)
{
bel[u] = cnt;
for (int i = head[u]; i != -1; i = adj[i].nex)
{
if ((i ^ 1) == fa || cut[i]) continue;
int v = adj[i].to;
if (bel[v]) continue;
DFS(v, i);
}
}
void traverse()
{
for (int i = 1; i <= n; ++ i)
if (!dfn[i])
Tarjan(i, -1);
for (int i = 1; i <= n; ++ i)
if (!bel[i])
{
++ cnt;
DFS(i, -1);
}
}
int dgr[MAXN];
int main()
{
n = in();
m = in();
memset(head, -1, sizeof head);
for (int i = 1; i <= m; ++ i)
{
int u = in(), v = in();
link(u, v);
}
traverse();
for (int u = 1; u <= n; ++ u)
{
for (int i = head[u]; i != -1; i = adj[i].nex)
{
int v = adj[i].to;
if (bel[u] == bel[v]) continue;
++ dgr[bel[u]], ++ dgr[bel[v]];
}
}
int ans = 0;
for (int i = 1; i <= cnt; ++ i)
if (dgr[i] == 2) ++ ans;
printf("%d
", (ans + 1) / 2);
return 0;
}
点双连通分量和割点
判断:
- 因为树根没有祖先, 所以当然(low[v])都(ge dfn[u]), 即子树内最早只能回到自己, 所以这样判定是无效的, 要以子树个数来判断, 即(child>1)
- 否则, 某个儿子(没访问过的点) 的(low[v]ge dfn[u]), 即某个子树内所有的点都不能沿树边跳到更高位置; 而不能用已访问过点判断, 因为假如他在某个子树中, 那么只能代表这个子树的某一个点不能跳回, 其他不能确定
代码在下面(bzoj2730割点, 点双)
BZOJ2730: [HNOI2012]矿场搭建
题意:
有一张连通图, 要在上面放一些出口, 使得任意删去一点时, 其余点都能到达某个出口, 求最少出口数, 和方案数
Sol:
(二周目)
无割点时很简单, 注意至少放两个而不是一个
对于有割点, 并不是每个点双都要放, 仔细一想可以知道只有"叶子连通块"需要放
(以删去的点为根, 那么每棵子树都要有一个出口)
我的做法是, 标记一下子树放过没, 注意: 如果 (low[v]<dfn[u]) 的子树放过了也算放过了, 也要继承. 为了方便处理树根, 我再次用割点为根跑一次 Tarjan 来算答案
理性的做法: 分析点双, 发现只有包含一个割点的点双没有出路("叶子连通块")(想想为什么?显然, 一个点双只能从 cut 出去); 所以遍历点双数割点即可
LL ans1, ans2;
int idx, low[MAXN], dfn[MAXN];
bool cut[MAXN], nocut;
void Tarjan(int u, int fa)
{
low[u] = dfn[u] = ++ idx;
int ch = 0;
for (int i = head[u]; i != -1; i = adj[i].nex)
{
if ((fa ^ 1) == i) continue;
int v = adj[i].to;
if (!dfn[v])
{
Tarjan(v, i);
low[u] = min(low[u], low[v]);
if (fa == -1) ++ ch;
if ((fa != -1 && low[v] >= dfn[u]) || (fa == -1 && ch > 1))
cut[u] = true, nocut = false;
}
else low[u] = min(low[u], dfn[v]);
}
}
int top, stk[MAXN];
void DFS(int u, int fa)
{
stk[++ top] = u;
dfn[u] = 1;
if (cut[u]) return;
for (int i = head[u]; i != -1; i = adj[i].nex)
{
int v = adj[i].to;
if ((fa ^ 1) == i || dfn[v]) continue;
// printf("%d --> %d
", u ,v);
DFS(v, i);
}
}
void init()
{
nume = 0;
memset(head, -1, sizeof head);
n = 0;
ans1 = 0; ans2 = 1;
idx = 0;
memset(low, 0, sizeof low);
memset(dfn, 0, sizeof dfn);
memset(cut, false, sizeof cut);
nocut = true;
}
int main()
{
int t = 0;
while (true)
{
m = in();
if (!m) break;
init();
printf("Case %d: ", ++ t);
for (int i = 1; i <= m; ++ i)
{
int u = in(), v = in();
n = max(n, max(u, v));
link(u, v);
}
for (int i = 1; i <= n; ++ i)
if (!dfn[i]) Tarjan(i, -1);
memset(dfn, 0, sizeof dfn);
for (int i = 1; i <= n; ++ i)
if (!cut[i] && !dfn[i])
{
int numcut = 0; top = 0;
DFS(i, -1);
for (int j = 1; j <= top; ++ j) if (cut[stk[j]]) ++ numcut, dfn[stk[j]] = 0;
if (numcut == 1) ++ ans1, ans2 *= 1LL * (top - 1);
}
if (nocut) printf("2 %lld
", 1LL * n * (n - 1) / 2);
else printf("%lld %lld
", ans1, ans2);
}
return 0;
}
BZOJ1123: [POI2008]BLO-Blockade <割点应用>
题意:
给定一张无向图，求每个点被封锁之后有多少个有序点对 ((x,y)(x
e y,1le x,yle n)) 满足 (x) 无法到达 (y)
Sol:
(二周目)
- 非割点很简单: 只有自己和其他点无法到达
- 割点: 自己和其他点无法到达, 子树之间无法到达
然后其实 Tarjan 就是一个 DFS , 所以可以在 Tarjan 中直接计算 siz 不需要再次 DFS
Floyd
(二周目)
https://blog.csdn.net/xianpingping/article/details/79947091
经典的递推式是这样的
那假如说 dis[i][j] 取最小值时 (k) 应当取某个值 (x), 而此时 dis[i][x] 或 dis[x][j] 并没有更新至最小值呢?
归纳法:
考虑一个子图 (T) , 在这个子图中他们之间 dis 都已经更新至最短路
他一开始是 ({1})
这时取 (T) 外一点 k , 尝试将这个点加入 (T),(之后依次从 2 到 n 加)
那就要去再次更新扩大的子图 (G = T + k + (k leftrightarrow i in T)) 内所有点对间距离:
- 于是枚举 (G) 中所有点对 ((i, j)) , 用 (dis[i][k] + dis[k][j]) 去更新
- 特别地, 对于点对 ((k, i in T)), k 到 i 的最短路一定可以用 某条边 ((k ightarrow j)) + 原子图中 (dis[j][i]) 表示, 那么这么更新即可
对于第 1 点, floyd 的式子正确性显然,
对于第 2 点, 你可以发现 floyd 的式子并不只枚举子图中点对, 他是 ([1, n]), 所以如果 (i in T) 的标号较小, 则已经更新完毕, 只是(概念上)未加入子图, 否则, 显然他在 ([1, k]) 子图之外, 不用管
于是总结一下, floyd 枚举到 k 时, [1, k] 的子图之间最短路更新完毕, 除此之外, 子图外部部分更新且满足之后的加点都只需要更新内部的即可
由此可得, 你以特定顺序枚举 k , 就可以完成特定的子图加点过程的模拟, 下面有例题
POJ2240 Arbitrage
给一些货币的兑换关系, 问能不找出一种兑换的路径, 起始与结束是同一种货币, 本金增加, 有重边自环
Sol:
初始设 (dis[i][i]=1.0) , 跑弗洛伊德(最长路), 看有没有 (dis[i][i]>1) 就可以了
HDU3631 Shortest Path
题意: 给出一张有向图, 节点数 (nle 300) , 有一些操作会激活一些点, 还有一些询问查询当前(x,y)间的最短路(只能经过激活的点)
Sol:
(二周目)
每次将激活的点作为中点做一遍(floyd), 未激活的点作为起终点都无所谓, 因为查询的时候假如起终点是未激活的直接判掉, 而且不可能将未激活的作为中点, 所以综上查询时的路径是不经过未激活的点的
其余的可以看上面有关 floyd 的解释
复杂度: (O(n^3+q)), 因为每个节点只更新一次
错因: 输出格式看错, 假如已经激活过了就不用再跑了, 而我忘记写 else 了
int n, m, q;
bool mark[MAXN];
LL dis[MAXN][MAXN];
int main()
{
int T = 0, first = 1;
while (~scanf("%d%d%d", &n, &m, &q))
{
if (!n && !m && !q) break;
if (first) first = 0;
else printf("
");
printf("Case %d:
", ++ T);
memset(dis, 0x3f3f3f, sizeof dis);
for (int i = 0; i < n; ++ i) dis[i][i] = 0, mark[i] = false;
for (int i = 1; i <= m; ++ i)
{
int u, v; LL w;
scanf("%d%d%lld", &u, &v, &w);
dis[u][v] = min(dis[u][v], w);
}
while (q --)
{
int opt; scanf("%d", &opt);
if (!opt)
{
int x; scanf("%d", &x);
if (mark[x]) printf("ERROR! At point %d
", x);
else
{
mark[x] = true;
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
dis[i][j] = min(dis[i][j], dis[i][x] + dis[x][j]);
}
}
else
{
int x, y; scanf("%d%d", &x, &y);
if (!mark[x] || !mark[y]) printf("ERROR! At path %d to %d
", x, y);
else
{
if (dis[x][y] == 4557430888798830399) printf("No such path
");
else printf("%lld
", dis[x][y]);
}
}
}
}
return 0;
}
拓扑排序
CF274D Lovely Matrix <加点>
给出一个(n*m(n*mle 10^5))的矩阵, 有一些格子的值是(-1), 代表可以任意填写
现在要求输出一个列的排序, 使得在这个排序下, 每行都是非减的((-1)就不用管了)
Sol:
拓扑排序
(Fake)
然而每行把所有大小关系建边会炸, 所以我糊了一个假算法, 把每个点向第一个比他大的点建边(针对有多个相同的, 因为连向更加大的肯定是错误的, 因为到时候这个第一个比他大的会连向更大的), 然而这个数据就可以叉掉
1 5
1 2 2 3 3 // 当更大的也有多个相同时
(Right)
正确做法是建立虚拟点
暴力建边中, 某一列向另一列连边, 表示此列必须在那一列之前
仍然有多种做法(以下都是每一行做一次, 因为行*列复杂度正确):
- 每个点向其数值连出入边, 然后相邻的数值连边, 注意自己连自己
- 离散这一行的数值, 然后前一个数值连自己, 自己连现在这个数值, 这样每个数值的点只与相邻数值的点有关, 且不会漏掉拓扑关系
错因: 乱糊算法, 考虑不全, 数值从(0)开始而不是(1)开始
int n, m, cnt, last, tot;
struct Node
{
int id, v;
} tmp[MAXN];
bool cmp(Node x, Node y) { return x.v < y.v; }
int idgr[MAXN];
queue <int> q;
int ans[MAXN], top;
int main()
{
n = in(); m = in();
tot = m;
for (int i = 1; i <= n; ++ i)
{
for (int j = 1; j <= m; ++ j)
tmp[j].v = in(), tmp[j].id = j;
sort(tmp + 1, tmp + m + 1, cmp);
++ tot;
tmp[0].v = -233;
for (int j = 1; j <= m; ++ j)
{
if (tmp[j].v == -1) continue;
if (tmp[j].v != tmp[j - 1].v) ++ tot;
addedge(tot - 1, tmp[j].id);
++ idgr[tmp[j].id];
addedge(tmp[j].id, tot);
++ idgr[tot];
}
}
for (int i = 1; i <= tot; ++ i)
if (!idgr[i]) q.push(i);
while (!q.empty())
{
int u = q.front(); q.pop();
ans[++ top] = u;
for (int i = head[u]; i; i = adj[i].nex)
{
int v = adj[i].to;
-- idgr[v];
if (!idgr[v]) q.push(v);
}
}
for (int i = 1; i <= tot; ++ i)
if (idgr[i])
return printf("-1
"), 0;
for (int i = 1; i <= top; ++ i) if (ans[i] <= m) printf("%d ", ans[i]);
return 0;
}
POJ3967 Ideal Path <字典序最小路>
(二周目)
一周目并没有记录...
题意:
有向图, 边权都是 1, 但是有颜色, 求 1 到 n 的最短路, 且字典序最小
Sol:
从 n 开始 BFS, 建出分层图, 再从 1 开始, 对于 1 层一起处理, 并且只保留字典序最小的路, 即选出当前最小颜色全部加进去
BZOJ2750: [HAOI2012]Road <边被任意最短路径经过次数>
题意:
有 (N(le 1500)) 个点, (M(le 5000)) 条有向边, 问每一条边被任意起终点的最短路经过的次数
Sol:
点数比较少, 枚举起点, 跑出最短路, 然后拓扑排序出最短路图(假如两点的 (dis) 之差为边权, 则此边为最短路边), 算出每个点进来的路径数和出去的路径数, 然后一条边的被经过的次数就可以算了
错因: 做出拓扑序后没用这个数组, 直接从 (n) 到 (1) 枚举了...
LL dis[MAXN];
priority_queue <PII, vector<PII>, greater<PII> > pq;
void Dij(int s)
{
while (!pq.empty()) pq.pop();
for (int i = 0; i <= n + 1; ++ i) dis[i] = INF;
dis[s] = 0; pq.push(mp(dis[s], s));
while (!pq.empty())
{
PII now = pq.top(); pq.pop();
if (now.first > dis[now.second]) continue;
int u = now.second;
for (int i = head[u]; i; i = adj[i].nex)
{
int v = adj[i].to; LL w = adj[i].w;
if (dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
pq.push(mp(dis[v], v));
}
}
}
}
int idgr[MAXN];
LL lef[MAXN], rig[MAXN], sum[MAXM];
queue <int> q;
int rec[MAXN], top;
void topo(int s)
{
memset(idgr, 0, sizeof idgr);
memset(lef, 0, sizeof lef);
memset(rig, 0, sizeof rig);
top = 0;
for (int u = 1; u <= n; ++ u)
for (int i = head[u]; i; i = adj[i].nex)
if (dis[u] + adj[i].w == dis[adj[i].to]) ++ idgr[adj[i].to];
while (!q.empty()) q.pop();
q.push(s); lef[s] = 1;
while (!q.empty())
{
int u = q.front(); q.pop();
rec[++ top] = u;
for (int i = head[u]; i; i = adj[i].nex)
{
if (dis[u] + adj[i].w != dis[adj[i].to]) continue;
int v = adj[i].to;
(lef[v] += lef[u]) %= MOD;
-- idgr[v];
if (!idgr[v]) q.push(v);
}
}
for (int j = top; j >= 1; -- j)
{
int u = rec[j]; rig[u] = 1;
for (int i = head[u]; i; i = adj[i].nex)
{
if (dis[u] + adj[i].w != dis[adj[i].to]) continue;
int v = adj[i].to;
(rig[u] += rig[v]) %= MOD;
}
}
for (int j = top; j >= 1; -- j)
{
int u = rec[j];
for (int i = head[u]; i; i = adj[i].nex)
{
if (dis[u] + adj[i].w != dis[adj[i].to]) continue;
int v = adj[i].to;
(sum[i] += lef[u] * rig[v] % MOD) %= MOD;
}
}
}
int main()
{
n = in(), m = in();
for (int i = 1; i <= m; ++ i)
{
int u = in(), v = in(), w = in();
addedge(u, v, w);
}
for (int i = 1; i <= n; ++ i)
{
Dij(i);
topo(i);
}
for (int i = 1; i <= m; ++ i) printf("%lld
", sum[i]);
return 0;
}
最短路
CodeChef - CLIQUED Bear and Clique Distances <加点>
有 (N(le 10^5)) 个城市, 所有边都是无向边, 没有重边子环, 前 (K(le N)) 个城市两两间有同一长度 (X) 的道路连接, 另外有 (M(le 10^5)) 条给定长度的边(无重边)
给出一个起点 (S) , 问到每个城市的最短距离
Sol:
看到边多又有共性, 那么就往 加点 的方向想想吧
为前 (K(le N)) 个城市建虚拟点, 每个点去这点花费 0 , 这个点到这些点为 X, 所有外部连进来的都连这个点
BZOJ 1880: [Sdoi2009]Elaxia的路线 <最长公共最短路>
给一张(N(le 1500))个点的无向图, 边数可能很大, 再给出两对点 ((s1, t1),(s2,t2)) , 求他们的最短路的最长公共长度(没有方向规定)
Sample Input
9 10
1 6 7 8
1 2 1
2 5 2
2 3 3
3 4 2
3 9 5
4 5 3
4 6 4
4 7 2
5 8 1
7 9 1
Sample Output
3Sample Input
4 4
1 4 2 3
1 2 10
2 4 9
1 3 1
3 4 2
Sample Output
2
Sol:
(二周目)
用 4 个点跑最短路, 判断一条边是不是最短路的边
用在两条路上都是最短路边的边建新图, 然后求最长路(可以拓扑)
Dijkstra or SPFA ?
- Dijkstra 用
priority_queue优化是(O((m+n)lg^m)), 堆的复杂度就是 (O(nlg^n)) 的, 这里要(m)次堆操作 - Dijkstra 朴素做法枚举 (n) 次, 每次再枚举找出最小未更新点, 这样是 (O(n^2+m))
- SPFA 是 (O(k m))
在这题里朴素的Dij更优秀
//SPFA
int dis[MAXN][MAXN];
bool vis[MAXN];
queue <int> q;
void SPFA(int s)
{
for (int i = 1; i <= n; ++ i) dis[s][i] = 0x3f3f3f, vis[i] = false;
while (!q.empty()) q.pop();
dis[s][s] = 0; vis[s] = true; q.push(s);
while (!q.empty())
{
int u = q.front(); q.pop();
vis[u] = false;
for (int i = head[u]; i; i = adj[i].nex)
{
int v = adj[i].to, w = adj[i].w;
if (dis[s][u] + w < dis[s][v])
{
dis[s][v] = dis[s][u] + w;
if (!vis[v]) vis[v] = true, q.push(v);
}
}
}
}
int dgr[MAXN];
void topo(bool flag)
{
memset(dis[0], 0, sizeof dis[0]);
memset(dgr, 0, sizeof dgr);
for (int u = 1; u <= n; ++ u)
for (int i = head[u]; i; i = adj[i].nex)
{
int v = adj[i].to, w = adj[i].w;
if (dis[s1][u] + w + dis[t1][v] != dis[s1][t1]) continue;
if (dis[s2][u] + w + dis[t2][v] != dis[s2][t2] && flag) continue;
if (dis[t2][u] + w + dis[s2][v] != dis[s2][t2] && !flag) continue;
++ dgr[v];
}
while (!q.empty()) q.pop();
for (int i = 1; i <= n; ++ i) if (!dgr[i]) q.push(i);
while (!q.empty())
{
int u = q.front(); q.pop();
ans = max(ans, dis[0][u]);
for (int i = head[u]; i; i = adj[i].nex)
{
int v = adj[i].to, w = adj[i].w;
if (dis[s1][u] + w + dis[t1][v] != dis[s1][t1]) continue;
if (dis[s2][u] + w + dis[t2][v] != dis[s2][t2] && flag) continue;
if (dis[t2][u] + w + dis[s2][v] != dis[s2][t2] && !flag) continue;
dis[0][v] = max(dis[0][v], dis[0][u] + w);
-- dgr[v];
if (!dgr[v]) q.push(v);
}
}
}
int main()
{
n = in(); m = in();
s1 = in(); t1 = in(); s2 = in(); t2 = in();
for (int i = 1; i <= m; ++ i)
{
int u = in(), v = in(), w = in();
link(u, v, w);
}
SPFA(s1); SPFA(t1); SPFA(s2); SPFA(t2);
topo(0); topo(1);
printf("%d
", ans);
return 0;
}
//Dij
int dis[MAXN][MAXN];
bool vis[MAXN];
void Dij(int s)
{
memset(vis, false, sizeof vis);
memset(dis[s], 0x3f3f3f, sizeof dis[s]);
dis[s][s] = 0;
for (int t = 1; t <= n; ++ t)
{
int u = 0, mn = 0x3f3f3f;
for (int i = 1; i <= n; ++ i) if (!vis[i] && dis[s][i] < mn) u = i, mn = dis[s][i];
vis[u] = true;
// printf("dis[%d][%d] = %d
", s, u, dis[s][u]);
for (int i = head[u]; i; i = adj[i].nex)
{
int v = adj[i].to, w = adj[i].w;
if (dis[s][u] + w <= dis[s][v]) dis[s][v] = dis[s][u] + w;
}
}
}
int dgr[MAXN];
bool judge(int u, int v, int w, bool flag)
{
if (dis[s1][u] + w + dis[t1][v] != dis[s1][t1]) return false;
if (flag) return (dis[s2][u] + w + dis[t2][v] == dis[s2][t2]);
else return (dis[t2][u] + w + dis[s2][v] == dis[s2][t2]);
}
queue <int> q;
void topo(bool flag)
{
memset(dis[0], 0, sizeof dis[0]);
memset(dgr, 0, sizeof dgr);
for (int u = 1; u <= n; ++ u)
for (int i = head[u]; i; i = adj[i].nex)
{
int v = adj[i].to, w = adj[i].w;
if (!judge(u, v, w, flag)) continue;
++ dgr[v];
}
while (!q.empty()) q.pop();
for (int i = 1; i <= n; ++ i) if (!dgr[i]) q.push(i);
while (!q.empty())
{
int u = q.front(); q.pop();
ans = max(ans, dis[0][u]);
for (int i = head[u]; i; i = adj[i].nex)
{
int v = adj[i].to, w = adj[i].w;
if (!judge(u, v, w, flag)) continue;
// printf("%d --> %d
", u, v);
dis[0][v] = max(dis[0][v], dis[0][u] + w);
-- dgr[v];
if (!dgr[v]) q.push(v);
}
}
}
int main()
{
n = in(); m = in();
s1 = in(); t1 = in(); s2 = in(); t2 = in();
for (int i = 1; i <= m; ++ i)
{
int u = in(), v = in(), w = in();
link(u, v, w);
}
Dij(s1); Dij(t1); Dij(s2); Dij(t2);
topo(0); topo(1);
printf("%d
", ans);
return 0;
}
NOIP2017D1T3 逛公园
题意: 给出有向图, 有边权可以为0非负, 设 1 到 n 最短路为 d , 则求出 1 到 n 长度 (le d + K) 的路径数
(K le 50)
50% (n, m le 2000) 无0边
70% 无0边
100% (n ,m le 2e5)
Sol:
好难啊, 自闭了
一开始想乘法计数, 然后因为不一定最短路于是可以有环, 不能拓扑, 这就很操蛋了
然后打算先不管 0 边, 考虑(n, m le 2000) 无0边的暴力
然后想到 DP, 于是想到跟 K 有关的 DP, K 很小
最终写了个假的
正解:
dp[i][j] 表示 1 到 i , 长度比 1 到 i 的最短路大 j 的路径的个数,
然后显然是个拓扑型的 DP
用记搜从 n 开始搜比较容易
判无限解只要找出 0 环即可, 我用的是 Tarjan 跑 0 边, 找 SCC
总结:
脑袋比较烫, 原先自己设的 DP 是 从 i 到 n, 比最短路大 j 的方案数,
其实是和正解一样的, 但是不知道为什么, 转移写的很怪(把最短路边当 0 , 其他正常边权), 显然错了
果然还是菜啊, 菜怎么办呢, 就 2 天了, 不知所措
差分约束
有一些大小关系, 通过变号, 求 前缀 等方式, 将他们简化成等式左边两个变量的差, 右边一个常量的形式
如 (dis[u]-dis[v]le w) 这样的形式, 然后用最短路/最长路求解
如上式, 就是最短路
负权环代表有问题
POJ3159 Candies <差分约束>
裸题
POJ1275 Cashier Employment <好题>
给出 (24) 个小时每个小时需要在位的职员个数, 以及 (N(le 1000)) 个应聘职员的开始工作事件, 每个人都会恰好工作 (8) 小时
问你最少需要雇佣几个职员
Sol;
咕咕咕
int r[30], cnt[30];
int sum[30];
void init()
{
memset(cnt, 0, sizeof cnt);
memset(r, 0, sizeof r);
}
int dis[MAXN], len[MAXN];
bool inq[MAXN];
queue <int> q;
bool judge(int x)
{
memset(head, 0, sizeof head); nume = 0;
memset(dis, 0x3f3f3f, sizeof dis);
memset(len, 0, sizeof len);
addedge(24, 0, -x); addedge(0, 24, x);
for (int i = 1; i <= 24; ++ i) addedge(i - 1, i, cnt[i]), addedge(i, i - 1, 0); // v - u <= w
for (int i = 1; i <= 7; ++ i) addedge(i, 16 + i, x - r[i]);
for (int i = 8; i <= 24; ++ i) addedge(i, i - 8, -r[i]);
while (!q.empty()) q.pop();
memset(inq, false, sizeof inq);
dis[0] = 0; inq[0] = true; q.push(0); len[0] = 1;
while (!q.empty())
{
int u = q.front(); q.pop(); inq[u] = false;
for (int i = head[u]; i; i = adj[i].nex)
{
int v = adj[i].to;
if (dis[u] + adj[i].w < dis[v])
{
dis[v] = dis[u] + adj[i].w;
len[v] = max(len[v], len[u] + 1);
if (len[v] > 25) return false;
if (!inq[v])
{
inq[v] = true;
q.push(v);
}
}
}
}
return dis[24] == x;
}
void solve()
{
int l = 0, r = n, ret = n + 1;
while (l <= r)
{
int mid = l + r >> 1;
if (judge(mid)) ret = mid, r = mid - 1;
else l = mid + 1;
}
if (ret == n + 1) printf("No Solution
");
else printf("%d
", ret);
}
int main()
{
int T = in();
while (T --)
{
init();
for (int i = 1; i <= 24; ++ i) r[i] = in();
n = in();
for (int i = 1; i <= n; ++ i) ++ cnt[in() + 1];
solve();
}
return 0;
}
/*
*/
最短路
01BFS
k短路
DAG分解
最短路树图
A*
连通性
边双点双区分
Dominator tree(支配树)
Bridges: The Final Battle(CF)
生成树
prim, kru, LCT
矩阵树定理
斯坦纳树(最短路径换根)
平面图最小生成树(MST on planar fraphs), 还有随机
平面图三角剖分
度数限制生成树
最小树形图
最小直径生成树
最小乘积生成树
k小生成树,
旁树
团
极大团 最大团
clique
BronKerbosch 退化路
流
最大密度子图
最小平均值环
最小割树
https://www.csie.ntnu.edu.tw/~u91029/matching.html
hall's marriage定理
cf northeastern collegiate contest A
树
莫队, 虚树
prufer序列
长链剖分
3569: DZY Loves Chinese II
2-sat
三元环
chordal图