Solução por Rogério Júnior
A solução por força bruta seria simplesmente testar todos os vértices como possíveis $$A$$, $$B$$, $$C$$ e $$D$$. Entretanto, note que para dados $$B$$ e $$C$$ fixos, não faz sentido escolher $$A_1$$ mais próximo de $$B$$ que $$A_2$$ se $$A_2$$ não aparecer como nenhum dos outros vértices escolhidos. Deste modo, temos apenas $$3$$ possibilidades para $$A$$: os $$3$$ vértices mais distantes de $$B$$ (partindo deles), visto que não faz sentido escolher um outro pois dentre eles sempre há pelo menos um que não é $$C$$ ou $$D$$. De modo semelhante, há apenas três possibilidades para $$D$$.
Seja $$\alpha(v) = {u_1, u_2, u_3}$$ de modo que a distância de $$u_i$$ para $$v$$ não é inferior à de nenhum vértice não contido em $$\alpha(v)$$ ($$\alpha(v)={u_1,u_2,u_3}, \forall 1\leq i \leq 3, j, d(u_i,v)\geq d(j,v)$$), ou seja $$\alpha(v)$$ são três vértices $$u_i$$ cujos valores $$d(u_i,v)$$ são máximos. De maneira semelhante, Seja $$\beta(v) = {u_1, u_2, u_3}$$ de modo que a distância de $$v$$ para $$u_i$$ não é inferior à de nenhum vértice não contido em $$\beta(v)$$
Como vimos, basta agora testarmos todos os valores possíveis para $$A$$, $$B$$, $$C$$ e $$D$$ da seguinte maneira: vamos testar, por força bruta, todos os possíveis valores de $$B$$ e $$C$$, então testaremos os três valores possíveis de $$A$$ ($$\alpha(B)$$) e os tr~\e possíveis valores de $$D$$ ($$\beta(D)$$). A complexidade é $$O(n^2)$$.
Segue o código para melhor entendimento:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <algorithm> | |
| #include <cstring> | |
| #include <vector> | |
| #include <queue> | |
| using namespace std; | |
| #define MAXN 3030 | |
| #define INF 0x3f3f3f3f | |
| #define PB push_back | |
| int n, m, dist[MAXN][MAXN], alpha[MAXN][3], beta[MAXN][3], maior, v1, v2, v3, v4; | |
| vector<int> lista[MAXN]; | |
| // BFS para calcularmos as distâncias entre vértices | |
| void bfs(int ori){ | |
| queue<int> fila; | |
| fila.push(ori); | |
| dist[ori][ori]=0; | |
| while(!fila.empty()){ | |
| int v=fila.front(); fila.pop(); | |
| for(int i=0; i<lista[v].size(); i++){ | |
| int u=lista[v][i]; | |
| if(dist[ori][u]==-1){ | |
| dist[ori][u]=dist[ori][v]+1; | |
| fila.push(u); | |
| } | |
| } | |
| } | |
| } | |
| int main(){ | |
| memset(dist, -1, sizeof dist); | |
| scanf("%d %d", &n, &m); | |
| // leio todas as arestas | |
| for(int i=1; i<=m; i++){ | |
| int v, u; | |
| scanf("%d %d", &v, &u); | |
| lista[v].PB(u); | |
| } | |
| // faço BFS em todos os vértices para calcular todas as distâncias | |
| for(int i=1; i<=n; i++) bfs(i); | |
| // calculo os valores de alpha de cada vértice i | |
| for(int i=1; i<=n; i++){ | |
| // procurando um j que supere algum dos valores salvos em alpha[i] | |
| for(int j=1; j<=n; j++){ | |
| // para isso, calculo a menor distância em alpha[i] | |
| int menor=INF, idx=-1; | |
| for(int k=0; k<3; k++) if(dist[alpha[i][k]][i]<menor) menor=dist[alpha[i][k]][i], idx=k; | |
| // e checo se d(j,i) a supera | |
| if(dist[j][i]>menor) alpha[i][idx]=j; | |
| } | |
| } | |
| // de maneira semelhante, calculo os valores de beta | |
| for(int i=1; i<=n; i++){ | |
| for(int j=1; j<=n; j++){ | |
| int menor=INF, idx=-1; | |
| for(int k=0; k<3; k++) if(dist[i][beta[i][k]]<menor) menor=dist[i][beta[i][k]], idx=k; | |
| // mas, agora, checo a d(i,j), não d(j,i) | |
| if(dist[i][j]>menor) beta[i][idx]=j; | |
| } | |
| } | |
| // agora testo todos os possíveis valores de A, B, C e D | |
| for(int i=0; i<3; i++) | |
| for(int v=1; v<=n; v++) | |
| for(int u=1; u<=n; u++) | |
| for(int j=0; j<3; j++){ | |
| int k=alpha[v][i], q=beta[u][j]; | |
| // se houver alguma repetição, tal escolha de A, B, C e D não é possível | |
| if(k==v or k==u or k==q) continue; | |
| if(v==u or v==q) continue; | |
| if(u==q) continue; | |
| // se algum deles for inalcançãvel a partir do anterior, também não é possível | |
| if(dist[k][v]<0 or dist[v][u]<0 or dist[u][q]<0) continue; | |
| // calculo o tamanho da rota | |
| int d=dist[k][v]+dist[v][u]+dist[u][q]; | |
| // e nvejo se ela é maior | |
| if(d>maior) maior=d, v1=k, v2=v, v3=u, v4=q; | |
| } | |
| // por fim, imprimo a reposta | |
| printf("%d %d %d %d\n", v1, v2, v3, v4); | |
| return 0; | |
| } |
Comente