图论基础
树和图的存储
模板
树是特殊的图，无向图是特殊的有向图，所以只需要考虑有向图的存储。
图的存储(邻接表) 适用于稀疏图
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e6;
int h[N], e[N], ne[N], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int main()
{
memset(h, -1, sizeof h);
return 0;
}图的存储(邻接矩阵) 适用于稠密图
图 DFS
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e6;
int h[N], e[N], ne[N], idx;
bool vis[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u)
{
vis[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!vis[u]) dfs(j);
}
}
int main()
{
memset(h, -1, sizeof h);
dfs(1);
return 0;
}图 BFS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
const int N = 1e5 + 10;
int n, m, h[N], e[N], ne[N], idx, dis[N];
bool vis[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int bfs()
{
queue<int> q;
q.push(1);
while (q.size())
{
auto t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!vis[j])
{
vis[j] = true;
dis[j] = dis[t] + 1;
q.push(j);
if (j == n) return dis[j];
}
}
}
return -1;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m; i ++)
{
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs() << endl;
return 0;
}应用
拓扑排序：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
const int N = 1e5 + 10;
int n, m, h[N], e[N], ne[N], idx, d[N], ans[N], cnt;
void add(int a, int b)
{
e[idx] = b, d[b] ++, ne[idx] = h[a], h[a] = idx ++;
}
void bfs()
{
queue<int> q;
for (int i = 1; i <= n; i ++)if (!d[i]) q.push(i);
while (q.size())
{
auto t = q.front();
ans[cnt ++] = t;
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
d[j] --;
if (!d[j])q.push(j);
}
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m; i ++)
{
int a, b;
cin >> a >> b;
add(a, b);
}
bfs();
if (cnt == n)
{
for (int i = 0; i < cnt; i ++) printf("%d ", ans[i]);
cout << endl;
}
else cout << -1 << endl;
return 0;
}最短路
反向建图
用反向图找到一条从A到B的道路后，若翻回原图，则路线会变成B到A。
因此，反向建图之后，跑一遍最短路(Dijkstra | SPFA)，得到的就是任意点到源点的最短路。
求最短路有几条
当访问到这个节点时，如果是第一次访问，将这个节点的答案+=他父节点的答案，并将这个节点推到队尾（push）；
如果是第二次访问且当前的距离等于之前记录的距离，说明这是第二条最短路，同样，将这个节点的答案+=他父节点的答案，但不需要（push）了。
操作计数
if(dist[j] > dist[t] + w[i])
{
cnt[j] = cnt[t];
}
else if (dist[j] == dist[t] + w[i])
{
cnt[j] += cnt[t];
cnt[j] %= mod;
}判负环
在找最短路的时候当经过的路径中有负环的时候，没经过该负环一次距离减小，重复经过这几个形成负环的点。根据鸽巢原理，n个点的最短路中最多经过n - 1个点，当经过的点数大于等于n的时候说明该路径中存在负环。因此，只需要在spfa中每次更新dist的时候统计经过的点数。
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;朴素Dijkstra
思路：
模板：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
const int N = 510;
int n, m, g[N][N], dist[N]; // g数组存边，dist数组表示从1到i点的最短距离
bool vis[N]; // 表示每个点的最短路是否已经确定
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 1; i < n; i ++)
{
int t = -1; // 在未确定最短路的点中找到距离起点最短的点
for (int j = 1; j <= n; j ++)
if (!vis[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
vis[t] = true;
}
if (dist[n] == INF) return -1;
return dist[n];
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
for (int i = 0; i < m; i ++)
{
int x, y, z;
cin >> x >> y >> z;
g[x][y] = min(g[x][y], z);
}
cout << dijkstra() << endl;
return 0;
}堆优化Dijkstra
思路：
模板：
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 10;
int n, m, h[N], e[N], ne[N], w[N], idx, dist[N];
bool vis[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<pii, vector<pii>, greater<pii>> q;
q.push({0, 1}); // first表示距离， second表示编号
while (q.size())
{
auto t = q.top();
q.pop();
int ver = t.second, distance = t.first;
if (vis[ver]) continue;
vis[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
q.push({dist[j], j});
}
}
}
if (dist[n] == INF) return -1;
return dist[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cout << dijkstra() << endl;
return 0;
}Bellman-Ford
思路：
模板：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
const int N = 1e5 + 10;
struct Edge
{
int a, b, w;
}edges[N];
int n, m, k, dist[N], backup[N];
int Bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i ++)
{
memcpy(backup, dist, sizeof dist);
for (int j = 0; j < m; j ++)
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], backup[a] + w);
}
}
if (dist[n] > INF / 2) return -1;
return dist[n];
}
int main()
{
cin >> n >> m >> k;
for (int i = 0; i < m; i ++)
{
cin >> edges[i].a >> edges[i].b >> edges[i].w;
}
int t = Bellman_ford();
if (t == -1) cout << "impossible" << endl;
else cout << t << endl;
return 0;
}SPFA求最短路
思路：
模板：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
const int N = 1e5 + 10;
int n, m, e[N], ne[N], idx, h[N], dist[N], w[N];
bool vis[N];
int SPFA()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
vis[1] = true;
queue<int> q;
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
vis[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (vis[j]) continue;
vis[j] = true;
q.push(j);
}
}
}
if (dist[n] == INF) return -1;
return dist[n];
}
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int t = SPFA();
if (t == -1) puts("impossible");
else cout << t << endl;
return 0;
}SPFA判负环
思路：
模板：
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
const int N = 1e6;
int n, m, h[N], e[N], ne[N], idx, dist[N], w[N], cnt[N];
bool vis[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool SPFA()
{
queue<int> q;
for (int i = 1; i <= n; i ++)
{
q.push(i);
vis[i] = true;
}
while (q.size())
{
int t = q.front();
q.pop();
vis[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!vis[j])
{
vis[j] = true;
q.push(j);
}
}
}
}
return false;
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if (SPFA()) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}Floyd
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
const int N = 1e3;
int n, m, k, d[N][N];
void Floyd()
{
for (int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main()
{
cin >> n >> m >> k;
memset(d, 0x3f, sizeof d);
for (int i = 1; i <= n; i ++) d[i][i] = 0;
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
d[a][b] = min(d[a][b], c);
}
Floyd();
for (int i = 0; i < k; i ++)
{
int x, y;
cin >> x >> y;
if (d[x][y] > INF >> 1) cout << "impossible" << endl;
else cout << d[x][y] << endl;
}
return 0;
}最短路应用
洛谷题单
P3371 【模板】单源最短路径（弱化版）
解法1(堆优化Dijkstra)：
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 10;
int m, n, s, e[N], ne[N], idx, w[N], h[N], dist[N];
bool vis[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void dijkstra()
{
for (int i = 1; i <= n; i ++) dist[i] = 2147483647;
dist[s] = 0;
priority_queue<pii, vector<pii>, greater<pii> > heap;
heap.push({0, s});
while (heap.size())
{
pii t = heap.top();
heap.pop();
int ver = t.second, d = t.first;
if (vis[ver]) continue;
vis[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > w[i] + d)
{
dist[j] = w[i] + d;
heap.push({dist[j], j});
}
}
}
}
int main()
{
scanf("%d%d%d", &n, &m, &s);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
dijkstra();
for (int i = 1; i <= n; i ++) printf("%d ", dist[i]);
return 0;
}解法2(朴素Dijkstra)：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
const int N = 1e6 + 10;
int n, m, s, dist[N], e[N], ne[N], idx, h[N], w[N];
bool vis[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void dijkstra()
{
for (int i = 1; i <= n; i ++) dist[i] = 2147483647;
dist[s] = 0;
for (int i = 1; i < n; i ++)
{
int t = -1;
for (int j = 1; j <= n; j ++)
if (!vis[j] && (t == -1 || dist[t] > dist[j]))
t = j;
for (int j = h[t]; j != -1; j = ne[j])
{
int k = e[j];
dist[k] = min(dist[k], dist[t] + w[j]);
}
vis[t] = true;
}
}
int main()
{
cin >> n >> m >> s;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
dijkstra();
for (int i = 1; i <= n; i ++) printf("%d ", dist[i]);
return 0;
}解法3(SPFA)：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
const int N = 1e6;
int n, m, s, e[N], ne[N], idx, w[N], h[N], dist[N];
bool vis[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void SPFA()
{
for (int i = 1; i <= n; i ++) dist[i] = 2147483647;
dist[s] = 0;
queue<int> q;
q.push(s);
vis[s] = true;
while (q.size())
{
int t = q.front();
q.pop();
vis[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!vis[j])
{
vis[j] = true;
q.push(j);
}
}
}
}
}
int main()
{
cin >> n >> m >> s;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
SPFA();
for (int i = 1; i <= n; i ++) printf("%d ", dist[i]);
return 0;
}P1629 邮递员送信
反向建图，将多源一汇最短路变为单源最短路。
解法1(朴素Dijkstra + 反向建图)：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e3 + 10;
int n, m, g[N][N], dist[N];
bool vis[N];
void Dijkstra()
{
memset(dist, 0x3f, sizeof dist);
memset(vis, 0, sizeof vis);
dist[1] = 0;
for (int i = 1; i < n; i ++)
{
int t = -1;
for (int j = 1; j <= n; j ++)
if (!vis[j] && (t == -1 || dist[t] > dist[j]))
t = j;
for (int j = 1; j <= n; j ++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
vis[t] = true;
}
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
Dijkstra();
int ans = 0;
for (int i = 1; i <= n; i ++) ans += dist[i];
for (int i = 1; i <= n; i ++) for (int j = i; j <= n; j ++) swap(g[i][j], g[j][i]);
Dijkstra();
for (int i = 1; i <= n; i ++) ans += dist[i];
cout << ans << endl;
return 0;
}解法2(堆优化Dijkstra + 反向建图)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 10;
int n, m, e[N], ne[N], h[N], w[N], idx, dist[N];
bool vis[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void Dijkstra(int start)
{
memset(dist, 0x3f, sizeof dist);
memset(vis, 0, sizeof vis);
dist[start] = 0;
priority_queue<pii, vector<pii>, greater<pii> > heap;
heap.push({0, start}); // first distance seconde node
while (heap.size())
{
pii t = heap.top();
heap.pop();
int distance = t.first, ver = t.second;
if (vis[ver]) continue;
vis[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b + n, a + n, c);
}
int ans = 0;
Dijkstra(1);
for (int i = 2; i <= n; i ++) ans += dist[i];
Dijkstra(1 + n);
for (int i = 2 + n; i <= 2 * n; i ++) ans += dist[i];
cout << ans << endl;
return 0;
}解法3(SPFA + 反向建图)：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
const int N = 1e6;
int n, m, e[N], ne[N], h[N], w[N], idx, dist[N];
bool vis[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void SPFA(int start)
{
memset(vis, 0, sizeof vis);
memset(dist, 0x3f, sizeof dist);
dist[start] = 0;
queue<int> q;
q.push(start);
vis[start] = true;
while (q.size())
{
int t = q.front();
q.pop();
vis[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!vis[j])
{
vis[j] = true;
q.push(j);
}
}
}
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b + n, a + n, c);
}
int ans = 0;
SPFA(1);
for (int i = 2; i <= n; i ++) ans += dist[i];
SPFA(1 + n);
for (int i = 2 + n; i <= n * 2; i ++) ans += dist[i];
cout << ans << endl;
return 0;
}P4779 【模板】单源最短路径（标准版）
解法1(SPFA):
被卡了
解法2(堆优化Dijkstra)：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6;
int n, m, s, e[N], ne[N], h[N], w[N], idx, dist[N];
bool vis[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void Dijkstra(int start)
{
memset(dist, 0x3f, sizeof dist);
dist[start] = 0;
priority_queue<pii, vector<pii>, greater<pii> > heap;
heap.push({0, start});
while (heap.size())
{
pii t = heap.top();
heap.pop();
int distance = t.first, ver = t.second;
if (vis[ver]) continue;
vis[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
}
int main()
{
cin >> n >> m >> s;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
Dijkstra(s);
for (int i = 1; i <= n; i ++) printf("%d ", dist[i]);
return 0;
}P1144 最短路计数
解法1(SPFA + 操作计数)
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
const int mod = 100003;
const int N = 1e7;
int n, m, h[N], e[N], ne[N], idx, dist[N], cnt[N];
bool vis[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void SPFA()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
cnt[1] = 1;
vis[1] = true;
queue<int> q;
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
vis[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + 1)
{
dist[j] = dist[t] + 1;
cnt[j] = cnt[t];
if (!vis[j])
{
vis[j] = true;
q.push(j);
}
}
else if (dist[j] == dist[t] + 1)
{
cnt[j] += cnt[t];
cnt[j] %= mod;
}
}
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++)
{
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
SPFA();
for (int i = 1; i <= n; i ++) cout << cnt[i] << endl;
return 0;
}解法2(堆优化Dijkstra + 操作计数)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e7;
const int mod = 100003;
int n, m, e[N], ne[N], h[N], idx, dist[N], ans[N];
bool vis[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void Dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
ans[1] = 1;
priority_queue<pii, vector<pii>, greater<pii> > heap;
heap.push({0, 1});
while(heap.size())
{
pii t = heap.top();
heap.pop();
int distance = t.first, ver = t.second;
if (vis[ver]) continue;
vis[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + 1)
{
ans[j] = ans[ver];
dist[j] = distance + 1;
heap.push({dist[j], j});
}
else if (dist[j] == distance + 1)
{
ans[j] += ans[ver];
ans[j] %= mod;
}
}
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
Dijkstra();
for (int i = 1; i <= n; i ++) cout << ans[i] << endl;
return 0;
}解法3(BFS)：
待写单源最短路建图方式
单源最短路的综合应用
单源最短路的扩展应用
最小生成树
概念
- 连通图：在无向图中，若任意两个顶点
vi与vj都有路径相通，则称该无向图为连通图。 - 强连通图：在有向图中，若任意两个顶点
vi与vj都有路径相通，则称该有向图为强连通图。 - 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
- 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
- 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
朴素Prim
思路
1、初始化所有点到集合中的最短距离为INF，然后遍历n次，将所有点都加入集合。
2、在每次遍历的时候，选取一个距离集合的距离最小的点加入集合，然后用这个点来更新其它未在集合中的点到集合的最小值。
模板
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 510;
int n, m, mp[N][N], dist[N];
bool vis[N];
int prim()
{
memset(dist, 0x3f, sizeof dist);
int sum = 0;
for (int i = 0; i < n; i ++)
{
int t = -1;
for (int j = 1; j <= n; j ++)
if (!vis[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (i && dist[t] == INF) return INF;
if (i) sum += dist[t]; // sum 在用t更新其它点之前更新，避免负环的影响
vis[t] = true;
for (int j = 1; j <= n; j ++) // 用t来更新其它点到集合的距离
dist[j] = min(dist[j], mp[t][j]);
}
return sum;
}
int main()
{
cin >> n >> m;
memset(mp, 0x3f, sizeof mp);
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
mp[a][b] = mp[b][a] = min(mp[a][b], c);
}
int ans = prim();
if (ans == INF) cout << "impossible" << endl;
else cout << ans << endl;
return 0;
}Kruskal
思路
1、将所有边按照权重大小，从小到大排序 O(mlogm)
2、枚举每条边，如果两个点所在的集合没有联通，则将这条边加入集合，使两个集合合并成一个集合(并查集)
模板
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6;
int n, m, p[N];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
struct Edge
{
int a, b, w;
bool operator < (const Edge& A) const // 运算符重载，也可以直接写一个cmp函数
{
return w < A.w;
}
}Edges[N];
int Kruskal()
{
sort(Edges, Edges + m);
for (int i = 1; i <= n; i ++) p[i] = i;
int sum = 0, cnt = 0;
for (int i = 0; i < m; i ++)
{
int a = Edges[i].a, b = Edges[i].b, w = Edges[i].w;
a = find(a), b = find(b);
if (a != b)
{
cnt ++;
sum += w;
p[a] = b;
}
}
if (cnt < n - 1) return INF;
return sum;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i ++) cin >> Edges[i].a >> Edges[i].b >> Edges[i].w;
int res = Kruskal();
if (res == INF) puts("impossible");
else cout << res << endl;
return 0;
}二分图
概念
二分图：
1、顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻(百度百科)
2、图中换的边数为偶数，则可以将这个换分为两个不同的顶点集合，集合内没有边连接，集合间用这些边连接。
染色法
思路：
二分图中，一个连通块中边的数量为偶数，将整个连通块染色，如果没有出现矛盾则为二分图，出现矛盾则不是二分图。
模板：
