目录

主体内容：

1.最小生成树

2.最短路算法：

      Dij：单源最短路算法

      Floyd：多源最短路算法

      Bellman_Ford：可处理负权图，SPFA写法

3.DFS序：   快点我！

4.二分图匹配：匈牙利算法

5.TOPO排序：判断有向图是否存在环

---

主体内容：

      最短路算法（Dijkstra、Floyd、Bellman_Ford）、最小生成树（Kruskal）、二分图匹配、DFS序、topo排序、LCS（最长公共子序列）、RMQ。

 

最小生成树：

ac代码：

#include<bits/stdc++.h> using namespace std; struct NODE{ int u, v, w; friend bool operator < (NODE a , NODE b){ return a.w < b.w; } }G[105]; int pre[55]; void init(int p){ for(int i = 1; i <= p; i++){ pre[i] = i; } } int find(int x){ return pre[x] == x ? x : pre[x] = find(pre[x]); } int main(){ int p, r; while(cin >> p && p){ cin >> r; if(r == 0) { cout << "0" << endl; continue; } init(p); for(int i = 1; i <= r; i++){ int u, v, w; cin >> u >> v >> w; G[i].u = u, G[i].v = v, G[i].w = w; } sort(G + 1, G + 1 + r); int ans = 0; for(int i = 1; i <= r; i++){ int px = find(G[i].v); int py = find(G[i].u); if(px != py){ pre[px] = py; ans += G[i].w; } } cout << ans << endl; } return 0; }

 

最短路算法：

                                            Dij：单源最短路算法

ac代码：

#include<bits/stdc++.h> #define pb push_back #define mp make_pair using namespace std; const int inf = 0x3f3f3f3f; int n, m; int a[105][105]; bool vis[105]; int d[105]; void dij(int s){ for(int i = 1; i <= n; i++){ d[i] = a[1][i]; } d[1] = 0; vis[1] = 1; for(int i = 1; i <= n; i++){ int m = inf; int x = -1; for(int j = 1; j <= n; j++){ if(!vis[j] && d[j] <= m){ m = d[j]; x = j; } } if(x == -1) break; vis[x] = 1; for(int j = 1; j <= n; j++){ d[j] = min(d[j], d[x] + a[x][j]); } } } int main(){ while(cin >> n >> m && (n && m)){ memset(a, inf, sizeof(a)); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++){ a[i][i] = 0; } for(int i = 1; i <= m; i++){ int u, v, w; cin >> u >> v >> w; a[u][v] = min(a[u][v], w); a[v][u] = a[u][v]; } dij(1); cout << d[n] << endl; } return 0; }

                                         Floyd：多源最短路算法

ac代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int inf = 0x3f3f3f3f; int a[105][105]; int main(){ int n, m; while(cin >> n >> m && n){ memset(a, inf, sizeof(a)); for(int i = 1; i <= m; i++){ int u, v, w; cin >> u >> v >> w; a[u][v] = min(a[u][v], w); a[v][u] = a[u][v]; } for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(a[i][k] > a[i][j] + a[j][k]){ a[i][k] = a[i][j] + a[j][k]; a[k][i] = a[i][k]; } } } } cout << a[1][n] << endl; } return 0; }

                        Bellman_Ford：可处理负权图，SPFA写法

//SPFA 把起点塞入队列，枚举起点所有边，如果枚举边的中点没有被更新过则加入队列，直到队列为空 //PII中的first表示G[i]所连得点，second表示边权 #include<cstdio> #include<iostream> #include<algorithm> #include<vector> #include<cstring> #include<queue> #define pii pair<int, int> #define mp make_pair #define fi first #define se second #define pb push_back using namespace std; const int inf = 0x3f3f3f3f; vector<pii> G[205]; int d[205]; bool vis[205]; void SPFA(int s){ memset(d, inf, sizeof(d)); memset(vis, 0, sizeof(vis)); queue<int> P; //需要枚举的点 vis[s] = 1; d[s] = 0; P.push(s); while(!P.empty()){ int flag = P.front(); P.pop(); vis[flag] = 0;//******* for(int i = 0; i <= G[flag].size() - 1; i++){//枚举队首所连的所有点 if(d[G[flag][i].fi] > d[flag] + G[flag][i].se){//直接去此点和经过flag再去 d[G[flag][i].fi] = d[flag] + G[flag][i].se; if(!vis[G[flag][i].fi]){//如果此点没被枚举过加入队列 P.push(G[flag][i].fi); vis[G[flag][i].fi] = 1; } } } } } int main(){ int n, m; while(cin >> n >> m){ for(int i = 1; i <= m; i++){ int a, b, x; cin >> a >> b >> x; G[a].pb(mp(b, x)); G[b].pb(mp(a, x)); } int s, t; cin >> s >> t; SPFA(s); cout << (d[t] == inf ? -1 : d[t]) << endl; for(int i = 0; i <= n - 1; i++){ G[i].clear(); } } return 0; }

                                      DFS序：   快点我！

       

                                 二分图匹配：匈牙利算法

    AC代码：

#include<bits/stdc++.h> using namespace std; bool line[505][505]; int girl[505]; bool used[505]; int k, n, m; bool find(int x){ for(int i = 1; i <= m; i++){ if(line[x][i] && !used[i]){ used[i] = 1; if(girl[i] == 0 || find(girl[i])){ girl[i] = x; return 1; } } } return 0; } int main(){ while(cin >> k && k){ cin >> n >> m; memset(girl, 0, sizeof(girl)); memset(line, 0, sizeof(line)); for(int i = 1; i <= k; i++){ int a, b; cin >> a >> b; line[a][b] = 1; } int ans = 0; for(int i = 1; i <= n; i++){ memset(used, 0, sizeof(used)); if(find(i)) ans ++; } cout << ans << endl; } return 0; }

 

                            TOPO排序：判断有向图是否存在环

AC代码：

#include<bits/stdc++.h> using namespace std; #define pb push_back int n, m; int degree[505]; int ans[505]; vector<int>G[505]; int Topo(){ int now = 1; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(degree[j] == 0){ degree[j]--; ans[now++] = j; for(int k = 0; k < G[j].size(); k++){ degree[G[j][k]]--; } break; } } } return now - 1; } int main(){ while(cin >> n >> m){ memset(degree, 0, sizeof(degree)); memset(ans, -1, sizeof(ans)); for(int i = 1; i <= n; i++){ G[i].clear(); } for(int i = 1; i <= m; i++){ int a, b; cin >> a >> b; G[a].pb(b); degree[b]++; } int cnt = Topo(); for(int i = 1; i <= cnt - 1; i++){ cout << ans[i] << " " ; } cout << ans[cnt] << endl; } return 0; }