Solução por Rogério Júnior
A solução por força bruta seria simplesmente testar todos os vértices como possÃveis 
, 
, 
e 
. Entretanto, note que para dados e fixos, não faz sentido escolher 
mais próximo de que 
se não aparecer como nenhum dos outros vértices escolhidos. Deste modo, temos apenas 
possibilidades para : os vértices mais distantes de (partindo deles), visto que não faz sentido escolher um outro pois dentre eles sempre há pelo menos um que não é ou . De modo semelhante, há apenas três possibilidades para .
Seja 
de modo que a distância de 
para 
não é inferior à de nenhum vértice não contido em 
(
), ou seja são três vértices cujos valores 
são máximos. De maneira semelhante, Seja 
de modo que a distância de para não é inferior à de nenhum vértice não contido em 
Como vimos, basta agora testarmos todos os valores possÃveis para , , e da seguinte maneira: vamos testar, por força bruta, todos os possÃveis valores de e , então testaremos os três valores possÃveis de (
) e os tr~\e possÃveis valores de (
). A complexidade é 
.
Segue o código para melhor entendimento:
This file contains 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; | |
| } |