算法总结归纳（第十二天）（剩余的图论）
目录
一、图论
Ⅰ、spfa算法
spfa求最短路
题目链接：spfa求最短路
思路：
本题使用的是队列求解，思路与dijkstra有相似之处，使用邻接表进行存储，使用w数组存储每个边的权重，然后t表示上一层的结点，j表示它的儿子结点，dist[j] > dist[t] + w[i]来更新边长，从而使得边长变为最小。
代码：
#include<iostream>
using namespace std;
#include<cstring>
#include<queue>
const int N = 1e6 + 10;
int e[N], ne[N], h[N], w[N], idx;
int dist[N];
bool st[N], cnt;
int n, m;
void add(int a, int b, int c)
{
e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx ++;
}
int spfa()
{
memset(dist, 0x3f3f3f3f, sizeof(dist));
dist[1] = 0;
st[1] = true;
queue<int> q;
q.push(1);
while(q.size())
{
int t = q.front();
q.pop();
st[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(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
if(dist[n] == 0x3f3f3f3f){
cnt = true;
return 1;
}
return dist[n];
}
int main()
{
cin>>n>>m;
memset(h, -1, sizeof(h));
while( m -- )
{
int x, y, z;
cin>>x>>y>>z;
add(x, y, z);
}
int t = spfa();
if(cnt) puts("impossible");
else cout<<t;
return 0;
}spfa判断负环
题目链接：spfa判断负环
思路：
本题判断负环就是根据判断是否有环来判断，cnt数组用来判断当前点经过的边数有几条，如果大于n条边，说明经过了n + 1个点。
代码：
#include<iostream>
using namespace std;
#include<cstring>
#include<queue>
const int N = 1e5 + 10;
int idx, e[N], ne[N], h[N], w[N];
int n, m;
bool st[N];
int cnt[N], dist[N];
void add(int a, int b, int c)
{
e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++;
}
bool spfa()
{
queue<int> q;
for(int i = 1; i<=n; i++){
q.push(i);
st[i] = true;
}
while(q.size())
{
int t = q.front();
q.pop();
st[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(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main()
{
cin>>n>>m;
memset(h, -1, sizeof(h));
while( m -- )
{
int a, b, c;
cin>>a>>b>>c;
add(a, b, c);
}
if(spfa()) puts("Yes");
else puts("No");
return 0;
}Ⅱ、floyd算法
题目链接：floyd求最短路
思路：
floyd算法就是简单的三重循环，时间复杂度是n的三次方。
多源汇问题，具有多个源点，算法实现基于动态规划推出来的，直接背熟模板就可以。
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]);
}
}
}上面这段是核心代码，只需要背熟就好。具体推导可问度娘。
代码：
#include<iostream>
using namespace std;
const int N = 210, INF = 1e9;
int n, m, k, x, y, z;
int 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;
for(int i = 1; i <= n; i++){
for(int j = 1; j<=n; j++){
if(i == j) d[i][j] = 0;
else d[i][j] = INF;
}
}
while(m -- )
{
cin>>x>>y>>z;
d[x][y] = min(d[x][y], z);
}
floyd();
while( k -- )
{
cin>>x>>y;
if(d[x][y] > INF / 2) puts("impossible");
else cout<<d[x][y]<<endl;
}
return 0;
}Ⅲ、prime算法
题目链接：prime求最小生成树
思路：
prime判断最小生成树，就是使用一个dt数组表示当前数组距离生成树的距离大小，同时使用邻接矩阵g进行图的存储，st数组表示的是否已经存储进树里面。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int g[N][N];//存储图
int dt[N];//存储各个节点到生成树的距离
int st[N];//节点是否被加入到生成树中
int n, m;//n 个节点，m 条边
void prim()
{
memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数（10亿左右）
int res= 0;
dt[1] = 0;//从 1 号节点开始生成
for(int i = 0; i < n; i++)//每次循环选出一个点加入到生成树
{
int t = -1;
for(int j = 1; j <= n; j++)//每个节点一次判断
{
if(!st[j] && (t == -1 || dt[j] < dt[t]))//如果没有在树中，且到树的距离最短，则选择该点
t = j;
}
//如果孤立点，直返输出不能，然后退出
if(dt[t] == 0x3f3f3f3f) {
cout << "impossible";
return;
}
st[t] = 1;// 选择该点
res += dt[t];
for(int i = 1; i <= n; i++)//更新生成树外的点到生成树的距离
{
if(dt[i] > g[t][i] && !st[i])//从 t 到节点 i 的距离小于原来距离，则更新。
{
dt[i] = g[t][i];//更新距离
}
}
}
cout << res;
}
int main()
{
memset(g, 0x3f, sizeof(g));//各个点之间的距离初始化成很大的数
cin >> n >> m;//输入节点数和边数
while(m --)
{
int a, b, w;
cin >> a >> b >> w;//输出边的两个顶点和权重
g[a][b] = g[b][a] = min(g[a][b],w);//存储权重
//如果有重边，那么选择权重最小的那一个。
}
prim();
return 0;
}Ⅳ、kruskai算法
题目链接：kruskal算法求最小生成树
思路：
本题使用并查集的思路，开始每个点都是独立的，当合并之后，res加上边的权重，然后将两个点的祖宗合并，然后就相当于合并一条边，cnt表示合并的边的条数，n个点，说明至少有n - 1条边，如果小于n - 1,那说明图不连通。
代码：
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 2e5 + 10;
int p[N]; int n, m;
int cnt = 0, res = 0;//记录存进去的边长
struct E
{
int a, b, w;
bool operator < (const E& rhs){//通过边长进行排序
return this->w < rhs.w;
}
} edge[N];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void klskr()
{
for(int i = 1; i<=m; i++){
int pa = find(edge[i].a);
int pb = find(edge[i].b);
if(pa != pb){
res += edge[i].w;
p[pa] = pb;
cnt ++;
}
}
}
int main()
{
cin>>n>>m;
for(int i = 1; i<=n; i++) p[i] = i;
for(int i = 1; i<=m; i++){
int a, b, w;
cin>>a>>b>>w;
edge[i] = {a, b, w};
}
sort(edge + 1, edge + m + 1);
klskr();
if(cnt < n - 1)
{
cout<<"impossible";
return 0;
}
cout<<res;
return 0;
}Ⅴ、染色法判定二分图
题目链接：染色法判定二分图
思路：
使用邻接表存储图。dfs用来判断于结点染色与上一层结点是否相同。相同，说明不是二分图，不相同，说明是二分图。
代码：
#include<iostream>
using namespace std;
#include<cstring>
#include<algorithm>
const int N = 1e5 + 10, M = 2e5 + 10;
int idx, e[M], ne[M], h[N];
int color[N];
int n, m;
void add(int a, int b)
{
e[idx] = b; ne[idx] = h[a]; h[a] = idx ++ ;
}
bool dfs(int u, int c)
{
color[u] = c;
for(int i = h[u]; i != -1; i = ne[i])
{
int t = e[i];
if(!color[t])
{
if(!dfs(t, 3 - c)) return false;
}
else if(color[t] && color[t] != 3 - c)
{
return false;
}
}
return true;
}
int main()
{
memset(h, -1, sizeof(h));
cin>>n>>m;
while( m -- )
{
int a, b;
cin>>a>>b;
add(a, b); add(b, a);
}
for(int i = 1; i<=n; i++)
{
if(!color[i]){
if(!dfs(i, 1)){
puts("No");
return 0;
}
}
}
puts("Yes");
return 0;
}Ⅵ、匈牙利算法（二分图）
题目链接：匈牙利算法
思路
本题也是二分图类型，本题，match表示当前点是否有配对的点，如果有其它配对点或者没有配对点则可以和当前点配对，否则就不配对。
代码：
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, M = 1e5 + 10;
int e[M], ne[M], idx, h[N];
int match[N];
int n1, n2, m;
bool st[N];
void add(int a, int b)
{
e[idx] = b; ne[idx] = h[a]; h[a] = idx ++;
}
bool find(int x)
{
for(int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if(!st[j])
{
st[j] = true;
if(match[j] == 0 || find(match[j])){
match[j] = x;
return true;
}
}
}
return false;
}
int main()
{
scanf("%d%d%d", &n1, &n2, &m);
memset(h, -1, sizeof(h));
while( m -- )
{
int a, b;
cin>>a>>b;
add(a, b);
}
int res = 0;
for(int i = 1; i<=n1; i++){
memset(st, false, sizeof(st));
if(find(i)) res ++;
}
cout<<res;
return 0;
}