minhas informações de contato
Correspondência[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Índice
Ideias para resolução de problemas
O algoritmo de Floyd, nome completo do algoritmo Floyd-Warshall, é um algoritmo de programação dinâmica usado para resolver o problema do caminho mais curto entre todos os pares de vértices no gráfico. É adequado para gráficos direcionados ponderados e pode lidar com arestas de peso negativo (mas não gráficos contendo ciclos de peso negativo) e pode detectar se há ciclos de peso negativo no gráfico.
A ideia central do algoritmo do Floyd é a programação dinâmica, e suas etapas básicas são as seguintes:
A implementação do algoritmo de Floyd geralmente usa um loop triplo. O loop externo percorre todos os vértices intermediários k e os dois loops internos percorrem todos os pares de vértices (i, j) para verificar se existe um caminho mais curto.
Suponha que temos um gráfico ponderado G contendo n vértices, podemos usar uma matriz bidimensionaldist[][]
para armazenar o menor comprimento do caminho entre cada par de vértices. Inicialmente,dist[i][j]
é definido como o peso da aresta diretamente conectada no gráfico. Se não houver nenhuma aresta diretamente conectada entre i e j, então.dist[i][j]
Definido como infinito (indicando inacessível).
inicialização : Crie uma matriz n×n D, onde D[i][j] é inicializado com o peso da aresta direta de i a j no gráfico ou definido como infinito se não houver aresta direta entre i e j. Elemento diagonal D[i][i] = 0.
programaçao dinamica : Para cada vértice k (como vértice intermediário), atualize o caminho mais curto entre cada par de vértices i e j. É possível obter um caminho mais curto com k como ponto intermediário. A fórmula de atualização é: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). Isso significa que se o caminho de i para j se tornar mais curto via k como um vértice intermediário, atualize D[i][j].
Saída de resultado: Após n rodadas de iterações, cada elemento D[i][j] na matriz D tem o comprimento de caminho mais curto de i a j.
343. Classificação - Banco de Perguntas AcWing
- #include <algorithm>
- #include <bits/stdc++.h>
- #include <iostream>
- using namespace std;
-
- #define PII pair<int, int>
- #define fi first
- #define se second
- #define endl 'n'
- map<int, int> mp;
-
- const int N = 210, mod = 1e9 + 7;
- int T, n, m, k;
- int a[N], dist[N][N];
- PII ans[N];
-
- void floyd(int x) // 以 x 为中转点,更新其他点。
- {
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- dist[i][j] = min(dist[i][j], dist[i][x] + dist[x][j]);
- }
-
- bool pd() // 判断是否所有点都已确定
- {
- for (int i = 1; i <= n; i++) {
- int cnt = 0;
- for (int j = 1; j <= n; j++)
- if (dist[i][j] != 1e9)
- cnt++; // 当前点能到达的点数
- ans[i] = {cnt, i};
- for (int j = 1; j <= n; j++)
- if (i != j && dist[j][i] != 1e9)
- cnt++; // 能到达当前点的点数
- if (cnt != n)
- return 0;
- }
- sort(ans + 1, ans + n + 1);
- return 1;
- }
-
- int main() {
- while (cin >> n >> m && n) {
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= n; j++)
- if (i != j)
- dist[i][j] = 1e9;
-
- int flag = 0;
- for (int i = 1; i <= m; i++) {
- char a, t, b;
- cin >> a >> t >> b;
- int x = a - 'A' + 1, y = b - 'A' + 1; // 现在要加一条从 y 到 x 的边
-
- if (!flag && dist[x][y] != 1e9) // 发现已经从x能到y,出现矛盾
- {
- printf("Inconsistency found after %d relations.n", i);
- flag = 1;
- }
-
- dist[y][x] = 1;
- floyd(x), floyd(y); // 分别以 x 和 y 为中转点更新其他点
- if (!flag && pd()) { // 发现所有点都已确定
- printf("Sorted sequence determined after %d relations: ", i);
- for (int i = 1; i <= n; i++)
- cout << char(ans[i].se + 'A' - 1);
- printf(".n");
- flag = 1;
- }
- }
- if (!flag)
- printf("Sorted sequence cannot be determined.n"); // 无法确定
- }
-
- return 0;
- }
dist
A matriz bidimensional é inicializada até o infinito, o que significa que não há uma relação de ordem definida entre as desigualdades por padrão.dist
Matrix, usando o algoritmo de Floyd para atualizar o caminho mais curto entre todas as desigualdades, aqui está na verdade atualizando a relação de “prioridade” ou “ordenação”.