le mie informazioni di contatto
Posta[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Sommario
Idee per la risoluzione dei problemi
L'algoritmo di Floyd, il nome completo dell'algoritmo di Floyd-Warshall, è un algoritmo di programmazione dinamica utilizzato per risolvere il problema del percorso più breve tra tutte le coppie di vertici nel grafico. È adatto per grafici diretti ponderati e può gestire bordi di peso negativi (ma non grafici contenenti cicli di peso negativi) e può rilevare se sono presenti cicli di peso negativi nel grafico.
L'idea centrale dell'algoritmo di Floyd è la programmazione dinamica e i suoi passaggi fondamentali sono i seguenti:
L'implementazione dell'algoritmo di Floyd utilizza solitamente un triplo ciclo. Il ciclo esterno attraversa tutti i vertici intermedi k e i due cicli interni attraversano tutte le coppie di vertici (i, j) per verificare se esiste un percorso più breve.
Supponiamo di avere un grafo pesato G contenente n vertici, possiamo utilizzare un array bidimensionaledist[][]
per memorizzare la lunghezza del percorso più breve tra ciascuna coppia di vertici. Inizialmente,dist[i][j]
è impostato sul peso dell'arco direttamente connesso nel grafico Se non c'è alcun arco direttamente connesso tra i e j, alloradist[i][j]
Impostato su infinito (che indica irraggiungibile).
inizializzazione : Crea una matrice n×n D, dove D[i][j] è inizializzato al peso dell'arco diretto da i a j nel grafico, o impostato a infinito se non c'è alcun arco diretto tra i e j. Elemento diagonale D[i][i] = 0.
programmazione dinamica : Per ogni vertice k (come vertice intermedio), aggiorna il percorso più breve tra ogni coppia di vertici i e j È possibile ottenere un percorso più breve con k come punto intermedio. La formula di aggiornamento è: D[i][j] = min(D[i][j], D[i][k] + D[k][j]). Ciò significa che se il percorso da i a j si accorcia passando per k come vertice intermedio, aggiornare D[i][j].
Uscita del risultato: Dopo n cicli di iterazioni, ciascun elemento D[i][j] nella matrice D ha la lunghezza del percorso più breve da i a j.
343. Ordinamento - Banca delle domande 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
L'array bidimensionale è inizializzato all'infinito, il che significa che per impostazione predefinita non esiste una relazione di ordine definita tra le disuguaglianze.dist
Matrix, utilizzando l'algoritmo di Floyd per aggiornare il percorso più breve tra tutte le disuguaglianze, qui sta effettivamente aggiornando la relazione di "priorità" o "ordine".