最小生成树 poj1287http://poj.org/problem?id=1287
Kruskal算法，加边法。先按边权升序排列，判断两个端点在不在一个集合里，不在就加入（运用并查集）。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cstdlib> 6 #include<cmath> 7 #define lson l, m, rt<<1 8 #define rson m+1, r, rt<<1|1 9 #define IO ios::sync_with_stdio(false);cin.tie(0); 10 #define INF 1e9 11 #define MAXN 10010 12 const int MOD=1e9+7; 13 typedef long long ll; 14 using namespace std; 15 int n, m, pre[100010]; 16 typedef struct { 17 int x, y, w; 18 }Node; 19 Node node[100010]; 20 bool cmp(const Node a, const Node b) 21 { 22 return a.w<b.w; 23 } 24 int find(int x) 25 { 26 int r = x; 27 while(pre[r] != r){ 28 r = pre[r]; 29 } 30 return r; 31 } 32 int main() 33 { 34 while(cin >> n >> m, n){ 35 int sum = 0; 36 for(int i = 1; i <= n; i++){ 37 pre[i] = i; 38 } 39 for(int i = 0; i < m; i++){ 40 cin >> node[i].x >> node[i].y >> node[i].w; 41 } 42 sort(node, node+m, cmp); 43 for(int i = 0; i < m; i++){ 44 int fx = find(node[i].x); 45 int fy = find(node[i].y); 46 if(fx != fy){//判断在不在一个集合里 47 pre[fx] = fy; 48 sum += node[i].w; 49 } 50 } 51 cout << sum << endl; 52 } 53 return 0; 54 }
最短路 poj2387http://poj.org/problem?id=2387
Dijkstra算法（单源最短路径，且仅适用于权非负），第一层循环内，还有两个第二层循环，第一个为选择最小，第二个为发展更小。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cstdlib> 6 #include<cmath> 7 #define lson l, m, rt<<1 8 #define rson m+1, r, rt<<1|1 9 #define IO ios::sync_with_stdio(false);cin.tie(0); 10 #define INF 1e9 11 #define MAXN 10010 12 const int MOD=1e9+7; 13 typedef long long ll; 14 using namespace std; 15 int t, n, a[1010][1010], lowcost[1010], vis[1010]; 16 void dijkstra() 17 { 18 for(int i = 1; i <= n; i++){//n个点 19 int mini = INF, k = -1; 20 for(int j = 1; j <= n; j++){//先找与当前点相连的，未被访问过的且权最小的点 21 if(!vis[j]&&lowcost[j] < mini){ 22 mini = lowcost[j]; 23 k = j; 24 } 25 } 26 if(k == -1) break; 27 vis[k] = 1; 28 for(int j = 1; j <= n; j++){//从这个找到的点再向外层发展，只是发展，还没有选择。 29 if(!vis[j]&&lowcost[k]+a[k][j]<lowcost[j]){ 30 lowcost[j] = lowcost[k]+a[k][j]; 31 } 32 } 33 } 34 } 35 int main() 36 { 37 int x, y, w; 38 cin >> t >> n; 39 for(int i = 1; i <= n; i++){ 40 for(int j = 1; j <= n; j++){ 41 a[i][j] = INF; 42 } 43 } 44 for(int i = 0; i < t; i++){ 45 cin >> x >> y >> w; 46 a[x][y]=min(a[x][y], w); //注意两点间有多条路径，取最短 47 a[y][x] = a[x][y]; 48 } 49 for(int i = 1; i <= n; i++){ 50 lowcost[i] = INF; 51 } 52 lowcost[1] = 0;//初始化 53 dijkstra(); 54 cout << lowcost[n] << endl; 55 return 0; 56 }
dijkstra优先队列优化、vector容器、pair求最短路径的最小价值（替换）
https://vjudge.net/problem/Aizu-2249
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<stack> 8 #define lson l, m, rt<<1 9 #define rson m+1, r, rt<<1|1 10 #define INF 0x3f3f3f3f 11 typedef unsigned long long ll; 12 using namespace std; 13 int n, m, a, b, d, c; 14 int dist[10010]; 15 struct edge{ 16 int to, d, cost; 17 //edge(int a, int b, int c):to(a),d(b),cost(c){ } 18 }; 19 typedef pair<int, int> P;//first是定点到i的长度，second是i点的号 20 vector<edge> G[10010]; 21 void dijkstra() 22 { 23 priority_queue<P, vector<P>, greater<P> > q; 24 for(int i = 1; i <= n; i++) dist[i] = INF; 25 dist[1] = 0;//该题起点为1 26 q.push(P(0, 1)); 27 while(!q.empty()){ 28 P p = q.top(); q.pop(); 29 int v = p.second; 30 if(dist[v] < p.first) continue;//如果不是最短就跳过 31 for(int i = 0; i < G[v].size(); i++){ 32 edge e = G[v][i]; 33 if(dist[e.to] > dist[v]+e.d){//以v向其他更新 34 dist[e.to] = dist[v]+e.d; 35 q.push(P(dist[e.to], e.to)); 36 } 37 } 38 } 39 } 40 int main() 41 { 42 while(cin >> n >> m){ 43 if(!n&&!m) break; 44 for(int i = 0; i <= n; i++){ 45 G[i].clear(); 46 } 47 for(int i = 0; i < m; i++){ 48 cin >> a >> b >> d >> c; 49 G[a].push_back(edge{b, d, c}); 50 G[b].push_back(edge{a, d, c}); 51 } 52 dijkstra(); 53 /*for(int i = 1; i <= n; i++){ 54 cout << dist[i] << " "; 55 }*/ 56 int sum = 0; 57 for(int i = 2; i <= n; i++){ 58 int mini = INF; 59 for(int j = 0; j < G[i].size(); j++){ 60 edge e = G[i][j]; 61 if(dist[e.to]+e.d == dist[i]){//这里注意，一开始e.d错放到等式右边了 62 mini = min(mini, e.cost); 63 } 64 } 65 sum += mini; 66 } 67 cout << sum << endl; 68 } 69 return 0; 70 }
Floyd算法（多源最短路径，且可用于负权）https://vjudge.net/contest/220253#problem/J
D[][]存储两点权值，P[][]存储路径，即点到点经过哪个点。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cstdlib> 6 #include<cmath> 7 #include<vector> 8 #include<stack> 9 #include<queue> 10 #define lson l, m, rt<<1 11 #define rson m+1, r, rt<<1|1 12 #define IO ios::sync_with_stdio(false);cin.tie(0); 13 #define INF 0x3f3f3f3f 14 #define MAXN 500010 15 const int MOD=1e9+7; 16 typedef long long ll; 17 using namespace std; 18 int D[1010][1010], P[1010][1010]; 19 int a, b, n, m, w; 20 int main() 21 { 22 cin >> n >> m; 23 for(int i = 1; i <= n; i++){ 24 for(int j = 1; j <= n; j++){ 25 if(i==j) D[i][j] = 0; 26 else D[i][j] = INF; 27 P[i][j] = j;//初始化 28 } 29 } 30 for(int i = 0; i < m; i++){ 31 cin >> a >> b >> w; 32 D[a][b] = w<D[a][b]?w:D[a][b];//注意两点间路径不止一条 33 D[b][a] = D[a][b]; 34 } 35 for(int k = 1; k <= n; k++){//可能成为的中介点 枚举 36 for(int i = 1; i <= n; i++){//出发点 37 for(int j = 1; j <= n; j++){//到达点 38 if(D[i][j] > D[i][k]+D[k][j]){ 39 D[i][j] = D[i][k]+D[k][j]; 40 P[i][j] = P[i][k];//经过下标为k的点 41 } 42 } 43 } 44 } 45 for(int i = 1; i <= n; i++){ 46 for(int j = 1; j <= n; j++){ 47 cout << D[i][j] << " "; 48 } 49 cout << endl; 50 } 51 return 0; 52 }
1 int pfpath(int u, int v) { //打印最短路径 2 while(u != v) { 3 cout << u << " "; 4 u = P[u][v]; 5 } 6 cout << u << endl; 7 }
Bellman-Ford判断图中有无负圈https://cn.vjudge.net/problem/POJ-3259
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<stack> 8 #define lson l, m, rt<<1 9 #define rson m+1, r, rt<<1|1 10 #define INF 0x3f3f3f3f 11 typedef unsigned long long ll; 12 using namespace std; 13 int a[1010][1010], dist[1010]; 14 int k, kase, n, m, w, s, e, t; 15 typedef struct{ 16 int from, to; 17 int cost; 18 }Node; 19 Node node[10010]; 20 int solve() 21 { 22 memset(dist, 0, sizeof(dist));//可以检查出所有的负圈 23 for(int i = 1; i <= n; i++){ 24 for(int j = 0; j < 2*m+w; j++){ 25 Node e = node[j]; 26 if(dist[e.to] > dist[e.from]+e.cost){//边松弛 27 dist[e.to] = dist[e.from]+e.cost; 28 if(i == n) return 1; 29 } 30 } 31 } 32 return 0; 33 } 34 int main() 35 { 36 scanf("%d", &kase); 37 while(kase--){ 38 scanf("%d%d%d", &n, &m, &w); 39 for(int i = 0; i < 2*m; i++){ 40 scanf("%d%d%d", &s, &e, &t);//路是双向的 41 node[i].from = s; node[i].to = e; 42 node[i].cost = t; 43 i++; 44 node[i].from = e; node[i].to = s; 45 node[i].cost = t; 46 } 47 for(int i = 2*m; i < 2*m+w; i++){ 48 scanf("%d%d%d", &s, &e, &t);//虫洞是单向的 49 node[i].from = s; node[i].to = e; 50 node[i].cost = -t; 51 } 52 if(solve()) cout << "YES" << endl; 53 else cout << "NO" << endl; 54 } 55 return 0; 56 }
强连通分量 hdu1269http://acm.hdu.edu.cn/showproblem.php?pid=1269
Kosaraju算法：步骤1.搜索原图，后序压栈 2.按出栈顺序遍历逆图，几次就是几个连通分量
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cstdlib> 6 #include<cmath> 7 #include<vector> 8 #include<stack> 9 #define lson l, m, rt<<1 10 #define rson m+1, r, rt<<1|1 11 #define IO ios::sync_with_stdio(false);cin.tie(0); 12 #define INF 1e9 13 #define MAXN 10010 14 const int MOD=1e9+7; 15 typedef long long ll; 16 using namespace std; 17 int n, m, x, y, vis[10010], cnt; 18 stack<int> s; 19 vector<int> t[10010], rt[10010]; 20 void dfs1(int cur) 21 { 22 vis[cur] = 1; 23 for(int i = 0; i < t[cur].size(); i++){ 24 if(!vis[t[cur][i]]){ 25 dfs1(t[cur][i]); 26 } 27 } 28 s.push(cur); 29 } 30 void dfs2(int cur) 31 { 32 vis[cur] = 1; 33 for(int i = 0; i < rt[cur].size(); i++){ 34 if(!vis[rt[cur][i]]){ 35 dfs2(rt[cur][i]); 36 } 37 } 38 } 39 void kosaraju() 40 { 41 memset(vis, 0, sizeof(vis)); 42 for(int i = 1; i <= n; i++){ 43 if(!vis[i]){ 44 dfs1(i); 45 } 46 } 47 memset(vis, 0, sizeof(vis)); 48 for(int i = 1; i <= n; i++){ 49 int x = s.top(); 50 if(!vis[x]){ 51 dfs2(x); 52 cnt++; 53 } 54 s.pop(); 55 } 56 } 57 int main() 58 { 59 IO; 60 while(cin >> n >> m){//存在m和n只有一个为0的情况，不能,m,n 61 if(m == 0&&n == 0) break; 62 while(!s.empty()) s.pop(); 63 for(int i = 1; i <= n; i++){ 64 t[i].clear();rt[i].clear(); 65 }//必须初始化两个容器 66 for(int i = 0; i < m; i++){ 67 cin >> x >> y; 68 t[x].push_back(y); 69 rt[y].push_back(x); 70 } 71 cnt=0; 72 kosaraju(); 73 if(cnt > 1){ 74 cout << "No" << endl; 75 } 76 else cout << "Yes" << endl; 77 } 78 return 0; 79 }
拓扑排序 hdu1285http://acm.hdu.edu.cn/showproblem.php?pid=1285
用vector存一个结点的指向的其它结点，用indegree存每个节点的入度。用STL优先队列小顶堆。先选择入度为0的结点入队，然后循环，该节点指向的所有结点indegree--，判断有无入度为0的结点，有则入队，如此往复。因为是小顶堆所以保证了排列尽可能小。
拓扑排序还可以判断是否是有向五环图，相同的方法，最后判断加入拓扑序的点的个数与总数是否相等
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cstdlib> 6 #include<cmath> 7 #include<vector> 8 #include<stack> 9 #include<queue> 10 #define lson l, m, rt<<1 11 #define rson m+1, r, rt<<1|1 12 #define IO ios::sync_with_stdio(false);cin.tie(0); 13 #define INF 1e9 14 #define MAXN 10010 15 const int MOD=1e9+7; 16 typedef long long ll; 17 using namespace std; 18 int n, m, x, y, indegree[1010]; 19 vector<int> vec[1010]; 20 void topo() 21 { 22 int flag=0; 23 priority_queue<int, vector<int>, greater<int> > q; 24 for(int i = 1; i <= n; i++){ 25 if(!indegree[i]){ 26 q.push(i); 27 } 28 } 29 while(!q.empty()){ 30 int t = q.top(); 31 if(!flag){ 32 flag = 1; 33 cout << t; 34 } 35 else cout << " " << t; 36 q.pop(); 37 for(int i = 0; i < vec[t].size(); i++){ 38 indegree[vec[t][i]]--; 39 if(!indegree[vec[t][i]]){ 40 q.push(vec[t][i]); 41 } 42 } 43 } 44 cout << endl; 45 } 46 int main() 47 { 48 while(cin >> n >> m){ 49 memset(indegree, 0, sizeof(indegree)); 50 for(int i = 1; i <= n; i++){ 51 vec[i].clear(); 52 } 53 for(int i = 0; i < m; i++){ 54 cin >> x >> y; 55 vec[x].push_back(y); 56 indegree[y]++; 57 } 58 topo(); 59 } 60 return 0; 61 }