2023.7.18

常规
1

图论

抄OI-Wiki的

基础概念：

  • 即有向图、无向图、混合图、完全图、竞赛图、子图、导出子图、补图、二分图、树、基环树、链、菊花（某四个字母的算法的噩梦）、重边、自环……

图的存储

  • 邻接矩阵:空间O(n^2)

  • 邻接表/vector:空间O(n+m)

  • 链式前向星:如下↓

struct edge
{
  	int v;
  	int next;
  	int val; 
}e[MAX];
int head[MAX] ,eid;
void addedge(int x ,int y)
{
  	++eid;
  	e[eid].to = y;
  	e[eid].next = head[x];
  	head[x] = eid;
}
for(int i = head[u]; i;i = e[i].next)//遍历从一个点u出发的所有边
{
  	int v = e[i].to;
  	*&^%&*&^^&&%%&*;
}

最短路

floyd

Dijkstra:

  • 单源最短路，只适用无负环的图,贪心思想

  • if(d[v]>d[u]+W_{u,v}) d[v]=d[u]+W_{u,v}

SPFA它死了

  • 初始化和存储类似Dijkstra,每次取队首尝试松弛其相连的所有点

  • 复杂度O(nm)

  • 可用于含负权边的图最短路，可用于寻找负环

差分约束

x_1 - x_0 <= 2
x_2 - x_0 <= 7
x_3 - x_0 <= 8 → 图的类型
x_2 - x_1 <= 3
x_3 - x_2 <= 2

  • 若题目中存在负环，则无解

  • 若s和t不连通，则无解

例题：小K的农场

  • 思路：将所有不等号转化为大于号，建图求最长路（也是差分约束的思路）

例题：新年好

  • 思路：预处理出每个点的最短路(Dijkstra),枚举拜访的顺序

  • 时间复杂度:O(5!*nlogn)

例题：泽泽射门

  • 思路：n^3枚举传球的人是否被阻挡，若不会则建一条传球时间的边，然后所有人建一条与球门的边，然后跑最短路即可

例题：Car 的旅行路线

  • 思路：建边，跑最短路

例题：[最短路条数]

  • 思路：最短路计数f，在更新d时同时计算f

  • 若d[u] + w< d[v] 则f[v] = f[u]

  • 若d[u] + w== d[v] 则f[v] += f[u]

  • 直接跑Dijkstra即可

例题：狡猾的商人

思路：

  • 令a的前缀和为S，则可以推出$S_r$ - S_{l-1} = k,又可以推出$S_r$ - S_{l-1} <= k&& S_{l-1} - S_{r} <= (-k),即可进行差分约束

例题：飞行路线

思路：

  • 用dp的思想给状态加一维，令d[i]代表起点到x用了i条免费线路的最小花费

   if d[v][i]>=d[u][i]+w d[v][i]=d[u][i]+w
   if d[v][i]>=d[u][i-1] d[v][i]=d[u][i-1]

  • 本质是张分层图，把图分成k+1层，上一层的边的起点对下一层的相同边的终点连一条权值为0的边

  • 注意答案对每层的ans取min

例题：重要的城市

思路

  • 观察到n的范围很小，考虑floyd，用p[i][j]记录从i到j路上经过重要的中转点，若k对f[i][j]成功松弛，则将p[i][j]赋值为k

   if f[i][j]==f[i][k]+f[k][j]  p[i][j]=0;

  • 最后枚举所有(i,j)，把所有重要中转点排序、去重即可

例题：Geodetic集合

思路

  • floyd求最短路,对每个u，v枚举中转点k

   if f[u][k]+f[k][v]==f[u][v] 则k在l(u,v)内

  • 复杂度O(n^3)

优化

  • u,v各跑一次dijstra,判中转点

例题：Piggy Back S

思路

  • 若P>B+E，则不合体，若P<=B+E,则合体

  • 对B,E,终点分别跑Dijkstra

例题：雷雨

思路

  • 枚举所有点，分别做Dijkstra

例题：限制边数的最短路

思路

  • 分层图,floyd

   d[i][j][T] 从i到j经过T条边的最短路  
   d[i][j][T]=min(d[i][j][T],d[i][k][T-x]+d[k][j][x]

小组成员：邵品渊，邵品砚，蒋佳成，顾天泽，马天翔，陈继禹