Floyd
求无向图最小环问题
https://www.acwing.com/problem/content/346/
floyd是典型的插点算法,每次插入点k,为此,在点k被[插入前]可计算i-j-k这个环
即此时中间节点为:1~k-1,即我们已经算出了任意i<->j的最短道路,中间经过的节点可以为 (1,2,3,...,k-1)
我们只需枚举所有以k为环中最大节点的环即可。
pos[i][j]:i~j的最短路中经过的点是k(即由这个状态转移过来),且这个k是此路径中编号最大的点(除i,j)
const int N = 105; int n, m; int d[N][N], g[N][N]; int pos[N][N]; int path[N], cnt; void get_path(int i, int j) { if (!pos[i][j]) return; int k = pos[i][j]; get_path(i, k); path[cnt ++] = k; get_path(k, j); } int main() { cin >> n >> m; memset(g, 0x3f, sizeof g); while (m --) { int a, b, c; cin >> a >> b >> c; g[a][b] = g[b][a] = min(g[a][b], c); } int ans = INF; memcpy(d, g, sizeof d); for (int k = 1; k <= n; k ++) { // 枚举以k为最大编号的环 for (int i = 1; i < k; i ++) for (int j = i + 1; j < k; j ++) if ((LL)d[i][j] + g[i][k] + g[k][j] < ans) { // i->k->j->..->i ans = d[i][j] + g[i][k] + g[k][j]; cnt = 0; path[cnt ++] = k; path[cnt ++] = i; get_path(i, j); path[cnt ++] = j; } for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) if (d[i][j] > d[i][k] + d[k][j]) { d[i][j] = d[i][k] + d[k][j]; pos[i][j] = k; } } if (ans == INF) puts("No solution."); else { for (int i = 0; i < cnt; i ++) cout << path[i] << " \n"[i == cnt - 1]; } return 0; }
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
const int N = 105; int n, m; int d[N][N], g[N][N]; int pos[N][N]; int path[N], cnt; void get_path(int i, int j) { if (!pos[i][j]) return; int k = pos[i][j]; get_path(i, k); path[cnt ++] = k; get_path(k, j); } int main() { cin >> n >> m; memset(g, 0x3f, sizeof g); while (m --) { int a, b, c; cin >> a >> b >> c; g[a][b] = g[b][a] = min(g[a][b], c); } int ans = INF; memcpy(d, g, sizeof d); for (int k = 1; k <= n; k ++) { // 枚举以k为最大编号的环 for (int i = 1; i < k; i ++) for (int j = i + 1; j < k; j ++) if ((LL)d[i][j] + g[i][k] + g[k][j] < ans) { // i->k->j->..->i ans = d[i][j] + g[i][k] + g[k][j]; cnt = 0; path[cnt ++] = k; path[cnt ++] = i; get_path(i, j); path[cnt ++] = j; } for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) if (d[i][j] > d[i][k] + d[k][j]) { d[i][j] = d[i][k] + d[k][j]; pos[i][j] = k; } } if (ans == INF) puts("No solution."); else { for (int i = 0; i < cnt; i ++) cout << path[i] << " \n"[i == cnt - 1]; } return 0; }View Code
标签:总结,图论,get,int,提高,cnt,pos,++,path From: https://www.cnblogs.com/Leocsse/p/16870968.html