Solução Maior Menor Caminho

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:


#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;
}