Encontre "544 - Heavy Cargo" https://vo.homelinux.org/wiki/code/problems/UVA/544.html, es muito parecido a "Prova", eu tenho "AC"; con o siguiente algoritmo:
int Maximo(vector < vector < pair<int,int> > > adj,int s,int t)
{
//"s" nodo raiz e "t" destino
//"adj" vector de adjacencia adj[v], tem os nodos adjaventes a v, sea
//"w" adjacente a "v", entao adj[v][i].firts="w" e adj[v][i].second=Arco(v-w);
//"i" e indice do vector
bool esta[202]; //Ayuda si esta ou nao na fila
memset(esta,false,sizeof(esta));
Qini();
//Q es Max_Heap
for(int i=0;i<N;i++)
{
cap[i]=-INF;
esta[i]=true;
Qinsert(i);
//Inserto todos os nodos
}
cap[s]=0;//Da raiz
Qinc(s);//Actualizo prioridade
int w;
while(!Qvacia())
{
int v=QdelMax();//Obtengo Maximo
esta[v]=false;//Ja nao esta na fila
if(cap[v]==-INF)
break;
for(int i=0;i<adj[v].size();i++)
{
w=adj[v][i].first;
int val=cap[v];
if(val>adj[v][i].second)
val=adj[v][i].second;
//Val tem o valor do novo cap[w]
if(v==s)
{ //si "v" es la raiz, os valores de cap[w] sao arco v-w
cap[w]=adj[v][i].second;
Qinc(w);
}
else if(esta[w]&&(val>cap[w]))
{
//Se "val" es mayor a anteorior cap[w] actualiza
cap[w]=val;
Qinc(w);
}
}
}
return cap[t];
}
O tempo es O(AlogV), como da prova.O algoritmo retorna maximo cap[t], agora para da prova so tenia que obtener todos, o mesmo algoritmo.
Esta correcto?, espero comentarios..t+.
PDT: "Disculpen pelo Portunhol"
Fórum