一些有关图论的模板。
uiii_
·
·
算法·理论
最短路
dijkstra
Tip：无法处理负边权。
memset(d,0x3f,sizeof(d));
priority_queue< pair<int,int> > q;
q.push(make_pair(0,s));
d[s]=0;
while(!q.empty){
int u=q.top().second;
q.pop();
if(f[u]) continue;
f[u]=1;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(d[v]>d[u]+e[i].w){
d[v]=d[u]+e[i].w;
if(!f[v]) q.push(make_pair(-d[v],v));
}
}
}
SPFA
memset(d,0x3f,sizeof(d));
d[s]=0,f[s]=1;
queue<int> q;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop(),f[u]=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(d[v]>d[u]+e[i].w){
d[v]=d[u]+e[i].w;
if(!f[v]){
q.push(v);
f[v]=1;
}
}
}
}
判断负环
SPFA
memset(d,0x3f,sizeof(d));
d[s]=0,f[s]=1;
queue<int> q;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop(),f[u]=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(d[v]>d[u]+e[i].w){
d[v]=d[u]+e[i].w;
cnt[v]=cnt[u]+1;//统计前驱
if(cnt[v]>=n){
return false;//存在负环
}
if(!f[v]){
q.push(v);
f[v]=1;
}
}
}
}
次短路
- 求最短路过程中顺带更新次短路。（可重复走边须 SPFA ）
- 起点、终点各跑一次最短路，枚举各点。次短路即为某一条边长度 + 起点到一个端点最短 + 终点到另一端点最短。
有关连通性
Tarjan强连通分量
```cpp
int cnt,scc,dfn[],low[],f[],col[];
stack<int> s;
void Tarjan(int u){
dfn[u]=low[u]=++cnt;
s.push(u),f[u]=1;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
}else if(f[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
scc++;
int x=-1;
while(x!=u){
x=s.top();
s.pop();
f[x]=0;
col[x]=u;
}
}
}
```
### 割点
1. $u$ 为树根，且子树数量 $>1$。
2. $u$ 不为树根，存在树枝边 $(u,v)$ 满足 $dfn_u\leq low_v$。
$tmp$ 统计 dfs 树中 $u$ 的树枝边数，$c$ 储存割点，$c_0$ 为割点数量。
```cpp
int cnt,dfn[],low[],root,c[];
void Tarjan(int u,int fr){
dfn[u]=low[u]=++cnt;
int tmp=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!dfn[v]){
tmp++;
Tarjan(v);
low[u]=min(low[u],low[v]);
if((u==root && tmp>1) || (u!=root && dfn[u]<=low[v])){
if(!c[u]) c[0]++;
c[u]=1;
}
}else if(v!=fr){
low[u]=min(low[u],dfn[v]);
}
}
}
```
#### 点双连通分量
1. Tarjan 找割点并把 dfs 遍历点入栈。
找到割点就弹栈直到弹出割点。弹出点即为该点双连通分量节点。割点重新入栈。
dfs 结束时将栈弹空。所弹出点也为一个点双连通分量。
3. 省略根节点判断，将割点判断条件直接改为 $dfn_u\leq low_v$。
同上进行入栈弹栈（发现孤立点或符合条件点）。
### 割边（桥）
存在树枝边，满足 $dfn_u<low_v$。
```cpp
int cnt,dfn[],low[];
vector<int> b[];
void Tarjan(int u,int fr){
dfn[u]=low[u]=++cnt;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!dfn[v]){
tmp++;
Tarjan(v);
low[u]=min(low[u],low[v]);
if(dfn[u]<low[v]){
if(u<v) b[u].push_back(v);
else b[v].push_back(u);
}
}else if(v!=fr){
low[u]=min(low[u],dfn[v]);
}
}
}
```
#### 边双连通分量
1. Tarjan 找桥，dfs 点入栈。
找到桥就弹栈，直至栈顶为 dfs 树父节点。dfs 结束后将栈弹空。
2. 将无向图看作有向图，禁止走同一无向边拆分出的回边。
寻找该有向图 scc。scc 即为边双连通分量。
## 差分约束
n 元一次不等式组，形如 $x_i-x_j\le c_k$。均可变形为 $x_i\le x_j+c_k$，类似单源最短路转移式 $d_v\le d_u+w$，可将 $x_i$ 看作图中节点。
对于每个 $x_i-x_j\le c+k$，建立一条由 $j$ 到 $i$ 大小为 $c_k$ 的单向边。同时建立超级源点，与每个节点间有一条大小为 0 的边。
另：若 $x_i=x_j$ 则在 $i$ 、$j$ 间建立权值为 0 的双向边。
跑 SPFA，若存在负环则无解，否则 $x_i=d_i$ 即为一组合法解。