Introdução

Você está sozinho em uma ilha. O restante da humanidade está morto ( provavelmente devido ao bug no código do user12345 ). A Horda de Piratas Zumbis chegou à sua ilha e são infinitas. É hora de chutar a bunda ou mascar chiclete, e todos estão sem chiclete.

Problema

Nosso cenário apocalíptico é descrito por 2 números inteiros em uma única linha, me n. Na sua ilha, os postos avançados são numerados de 1 a m. As seguintes nlinhas cada contêm três números inteiros, x, y, e z, separados por um espaço. xe ysão os IDs exclusivos de dois postos avançados e zé o número de zumbis que serão encontrados no caminho entre eles.

Quando você viaja por um caminho, perde zmunição e mata zzumbis. Se você seguir o mesmo caminho novamente, encontrará o mesmo número de zumbis, infelizmente. Todos os postos avançados geram +1 de munição cada vez que você percorre um caminho. Você começa com 100 munições no posto avançado 1. Todos os postos avançados começam com 0 munição. Você morre imediatamente se não houver um caminho para o qual sua munição seja maior que o número de zumbis nesse caminho, e o restante de sua munição for convertido em mortes. Essa é a sua posição final.

Escreva um programa que produza o número máximo de zumbis que você pode matar para um determinado cenário. Se você pode matar um número infinito de zumbis, basta imprimir x.

Exemplo de entrada

5 6
1 2 4
2 3 4
3 1 4
2 4 10
2 5 10
1 1 50

Saída de exemplo

x

Suposições

• Um caminho estará entre dois postos avançados válidos. Ou seja, 1 <= x/ y<=m
• Se um caminho entre xe ynão estiver listado, não poderá ser percorrido
• Um caminho é bidirecional
• 1 m<<= 100
• 1 n<<= 500
• A entrada deve ser fornecida por meio de stdin, lida de um arquivo ou aceita como um único argumento para o programa, e deve seguir exatamente o formato do exemplo
• O tempo de execução do seu programa pode ser arbitrariamente grande, mas deve ser determinadamente finito

O código com o menor número de caracteres vence!

Java ( menos grotesco: 8415 5291 3301)

Está bem. Basicamente, estou envergonhado por ninguém ter enviado uma solução. Então, alguns dias atrás, comecei a tentar resolver esse problema, porque é ótimo. . Siga esse link para assistir ao meu progresso no GitHub.

Editar

Nova versão do solucionador, muito mais "golfada", com o verificador de ciclo corrigido conforme identificado pelo MT0. Ele também suporta rotas de avanço rápido, ajustáveis ​​alterando a quantidade de memória disponível para a VM. Última edição do BIG : percebi que havia alguns outros pequenos erros de índice e otimizações prematuras, que resultaram em uma falha ao considerar um número bastante grande de tipos de vitórias. Então isso é corrigido, com cuidado. A nova versão é menor e abaixo. Para nossa rota de referência, java -Xmx2GB ZombieHordeMinfaz o truque muito bem (esteja avisado, vai demorar um pouco).

Factóide legal

Em uma reviravolta fascinante, existem MUITAS soluções no comprimento 24, e meu solucionador encontra uma diferente da MT0, mas idêntica em princípio, exceto pelo fato de começar visitando os outros postos conectados 1. Fascinante! Totalmente contra a intuição humana, mas perfeitamente válida.

Destaques da solução

Então aqui está o meu. É (parcialmente) jogado, b / c é um solucionador exponencial de força quase bruta. Uso um algoritmo IDDFS (primeira pesquisa aprofundada de aprofundamento iterativo), por isso é um ótimo solucionador geral que não pula, por isso resolve as duas partes da pergunta do OP, a saber:

• Se uma rota vencedora for encontrada (zumbis infinitos), produza 'x'.
• Se todas as rotas terminarem em morte (zumbis finitos), produza o maior número de zumbis mortos.

Dê a ele energia, memória e tempo suficientes, e fará exatamente isso, até mapas de morte lenta. Passei mais tempo aprimorando esse solucionador e, embora mais possa ser feito, está um pouco melhor agora. Também integrei o conselho do MT0 sobre a melhor solução de zumbis infinitos e removi várias otimizações prematuras do meu verificador de vitórias que impediam a versão anterior de encontrá-lo, e agora encontro uma solução muito semelhante à que o MT0 descreveu.

Alguns outros destaques:

• Como mencionado, usa um IDDFS para encontrar a rota vencedora mais curta possível.
• Como é o DFS principal, ele também descobrirá se todas as rotas terminam com a morte de nosso herói e mantém o controle da "melhor" rota em termos da maioria dos zumbis mortos. Morrer um herói!
• Eu instrumentei o algoritmo para torná-lo mais interessante de assistir Removido para fins de golfe. Siga um dos links para o github para ver a versão não destruída.
• Também existem vários comentários, sinta-se à vontade para reimplementar a sua própria solução com base em minha abordagem ou me mostrar como isso deve ser feito!
• Avanço rápido da rota adaptável à memória
  • Até a memória do sistema disponível, acompanhará as "rotas finais" que não resultaram em morte.
  • Usando uma rotina de compactação e descompactação de rota sofisticada, o progresso de uma iteração anterior do IDDFS é restaurado para impedir a redescoberta de todas as rotas visitadas anteriormente.
  • Como um bônus lateral intencional, atua como um abate de rota sem saída. As rotas sem saída não são armazenadas e nunca serão visitadas novamente em profundidades futuras do IDDFS.

História do solucionador

• Tentei um monte de algoritmos de antecipação de uma etapa e, embora em cenários muito simples, eles funcionassem, no final das contas eles fracassam.
• Então, tentei um algoritmo de duas etapas, que era ... insatisfatório.
• Comecei a criar um lookahead de n passos, quando reconheci que essa abordagem é redutível ao DFS, mas o DFS é muito ... mais elegante.
• Ao construir o DFS, ocorreu-me que o IDDFS garantiria (a) a melhor rota HERO (morte) ou (b) o primeiro ciclo vencedor.
• Acontece que criar um verificador de ciclo de vitória é fácil, mas eu tive que passar por várias iterações muito, muito erradas, antes de chegar a um verificador comprovadamente bem-sucedido.
• Considerado o caminho de vitória do MT0 para remover três linhas de otimização prematura que tornaram meu algoritmo cego para ele.
• Adicionado um algoritmo de cache de rota adaptável que usará toda a memória fornecida para evitar refazer desnecessário do trabalho entre chamadas IDDFS e também seleciona rotas sem saída até os limites de memória.

O código (golfe)

Para o código (obtenha a versão não destruída aqui ou aqui ):

import java.util.*;public class ZombieHordeMin{int a=100,b,m,n,i,j,z,y,D=0,R,Z,N;int p[][][];Scanner in;Runtime rt;int[][]r;int pp;int dd;int[][]bdr;int ww;int[][]bwr;int[][]faf;int ff;boolean ffOn;public static void main(String[]a){(new ZombieHordeMin()).pR();}ZombieHordeMin(){in=new Scanner(System.in);rt=Runtime.getRuntime();m=in.nextInt();N=in.nextInt();p=new int[m+1][m+1][N+1];int[]o=new int[m+1];for(b=0;b<N;b++){i=in.nextInt();j=in.nextInt();z=in.nextInt();o[i]++;o[j]++;D=(o[i]>D?o[i]:D);p[i][j][++p[i][j][0]]=z;if(i!=j)p[j][i][++p[j][i][0]]=z;D=(o[j]>D?o[j]:D);}m++;}void pR(){r=new int[5000][m+3];r[0][0]=a;Arrays.fill(r[0],1,m,1);r[0][m]=1;r[0][m+1]=0;r[0][m+2]=0;ww=-1;pp=dd=0;pR(5000);}void pR(int aMD){faf=new int[D][];ff=0;ffOn=true;for(int mD=1;mD<=aMD;mD++){System.out.printf("Checking len %d\n",mD);int k=ffR(0,mD);if(ww>-1){System.out.printf("%d x\n",ww+1);for(int win=0;win<=ww;win++)System.out.printf(" %d:%d,%d-%d",win,bwr[win][0],bwr[win][1],bwr[win][2]);System.out.println();break;}if(k>0){System.out.printf("dead max %d kills, %d steps\n",pp,dd+1);for(int die=0;die<=dd;die++)System.out.printf(" %d:%d,%d-%d",die,bdr[die][0],bdr[die][1],bdr[die][2]);System.out.println();break;}}}int ffR(int dP,int mD){if(ff==0)return pR(dP,mD);int kk=0;int fm=ff;if(ffOn&&D*fm>rt.maxMemory()/(faf[0][0]*8+12))ffOn=false;int[][]fmv=faf;if(ffOn){faf=new int[D*fm][];ff=0;}for(int df=0;df<fm;df++){dS(fmv[df]);kk+=pR(fmv[df][0],mD);}fmv=null;rt.gc();return kk==fm?1:0;}int pR(int dP,int mD){if(dP==mD)return 0;int rT=0;int dC=0;int src=r[dP][m];int sa=r[dP][0];for(int dt=1;dt<m;dt++){for(int rut=1;rut<=p[src][dt][0];rut++){rT++;r[dP+1][0]=sa-p[src][dt][rut]+r[dP][dt];for(int cp=1;cp<m;cp++)r[dP+1][cp]=(dt==cp?1:r[dP][cp]+1);r[dP+1][m]=dt;r[dP+1][m+1]=rut;r[dP+1][m+2]=r[dP][m+2]+p[src][dt][rut];if(sa-p[src][dt][rut]<1){dC++;if(pp<r[dP][m+2]+sa){pp=r[dP][m+2]+sa;dd=dP+1;bdr=new int[dP+2][3];for(int cp=0;cp<=dP+1;cp++){bdr[cp][0]=r[cp][m];bdr[cp][1]=r[cp][m+1];bdr[cp][2]=r[cp][0];}}}else{for(int chk=0;chk<=dP;chk++){if(r[chk][m]==dt){int fR=chk+1;for(int cM=0;cM<m+3;cM++)r[dP+2][cM]=r[dP+1][cM];for(;fR<=dP+1;fR++){r[dP+2][0]=r[dP+2][0]-p[r[dP+2][m]][r[fR][m]][r[fR][m+1]]+r[dP+2][r[fR][m]];for(int cp=1;cp<m;cp++)r[dP+2][cp]=(r[fR][m]==cp?1:r[dP+2][cp]+1);r[dP+2][m+2]=r[dP+2][m+2]+p[r[dP+2][m]][r[fR][m]][r[fR][m+1]];r[dP+2][m]=r[fR][m];r[dP+2][m+1]=r[fR][m+1];}if(fR==dP+2&&r[dP+2][0]>=r[dP+1][0]){ww=dP+1;bwr=new int[dP+2][3];for(int cp=0;cp<dP+2;cp++){bwr[cp][0]=r[cp][m];bwr[cp][1]=r[cp][m+1];bwr[cp][2]=r[cp][0];}return 0;}}}dC+=pR(dP+1,mD);if(ww>-1)return 0;}for(int cp=0;cp<m+3;cp++)r[dP+1][cp]=0;}}if(rT==dC)return 1;else{if(ffOn&&dP==mD-1)faf[ff++]=cP(dP);return 0;}}int[]cP(int dP){int[]cmp=new int[dP*2+3];cmp[0]=dP;cmp[dP*2+1]=r[dP][0];cmp[dP*2+2]=r[dP][m+2];for(int zip=1;zip<=dP;zip++){cmp[zip]=r[zip][m];cmp[dP+zip]=r[zip][m+1];}return cmp;}void dS(int[]cmp){int[]lv=new int[m];int dP=cmp[0];r[dP][0]=cmp[dP*2+1];r[dP][m+2]=cmp[dP*2+2];r[0][0]=100;r[0][m]=1;for(int dp=1;dp<=dP;dp++){r[dp][m]=cmp[dp];r[dp][m+1]=cmp[dP+dp];r[dp-1][cmp[dp]]=dp-lv[cmp[dp]];r[dp][m+2]=r[dp-1][m+2]+p[r[dp-1][m]][cmp[dp]][cmp[dP+dp]];r[dp][0]=r[dp-1][0]+r[dp-1][cmp[dp]]-p[r[dp-1][m]][cmp[dp]][cmp[dP+dp]];lv[cmp[dp]]=dp;}for(int am=1;am<m;am++)r[dP][am]=(am==cmp[dP]?1:dP-lv[am]+1);}}

Obtenha o código do github aqui, para rastrear as alterações que eu fizer. Aqui estão alguns outros mapas que eu usei.

Exemplo de saída

Exemplo de saída para solução de referência:

    $ java -d64 -Xmx3G ZombieHordeMin > reference_route_corrected_min.out
    5 6 1 2 4 2 3 4 3 1 4 2 4 10 2 5 10 1 1 50
    Checking len 1
    Checking len 2
    Checking len 3
    Checking len 4
    Checking len 5
    Checking len 6
    Checking len 7
    Checking len 8
    Checking len 9
    Checking len 10
    Checking len 11
    Checking len 12
    Checking len 13
    Checking len 14
    Checking len 15
    Checking len 16
    Checking len 17
    Checking len 18
    Checking len 19
    Checking len 20
    Checking len 21
    Checking len 22
    Checking len 23
    Checking len 24
    25 x
     0:1,0-100 1:3,1-97 2:1,1-95 3:2,1-94 4:5,1-88 5:2,1-80 6:4,1-76 7:2,1-68 8:1,1-70 9:2,1-68 10:1,1-66 11:2,1-64 12:1,1-62 13:2,1-60 14:1,1-58 15:2,1-56 16:1,1-54 17:2,1-52 18:1,1-50 19:2,1-48 20:1,1-46 21:2,1-44 22:1,1-42 23:2,1-40 24:1,1-38

Leia a saída da rota assim step:: source, route-to-get-here- ammo. Portanto, na solução acima, você a leria como:

• No passo 0, no posto avançado 1com munição 100.
• Na etapa 1, use a rota 1para chegar ao posto avançado 3com o fim da munição97
• Na etapa 2, use a rota 1para chegar ao posto avançado 1com o fim da munição95
• ...

Notas finais

Então, espero que eu tenha dificultado minha solução, mas POR FAVOR TENTE! Use-o contra mim, adicione algum processamento paralelo, melhor teoria gráfica, etc. Algumas coisas que eu acho que poderiam melhorar essa abordagem:

• agressivamente "reduza" os loops para cortar desnecessariamente recauchutados à medida que o algoritmo progride.
  • Um exemplo: no problema de exemplo, considere os loops 1-2-3 e outras permutações como "uma etapa", para que possamos abrir caminho para o ciclo final mais rapidamente.
  • Por exemplo, se você estiver no nó 1, poderá (a) ir para 2, (b) ir para 1, (c) passar por 1-2-3 como uma etapa e assim por diante. Isso permitiria que um resolvido dobre a profundidade em amplitude, aumentando o número de rotas em uma profundidade específica, mas acelerando bastante o tempo de solução para ciclos longos.
• selecionar rotas mortas. Minha solução atual não "lembra" que uma rota específica é sem saída e precisa redescobri-la sempre. Seria melhor acompanhar o primeiro momento de uma rota em que a morte é certa e nunca progredir além dela. fez isso...
• se for cuidadoso, você pode aplicar a seleção de rota morta como uma seleção de sub-rota. Por exemplo, se 1-2-3-4 sempre resulta em morte, e o solucionador está prestes a testar a rota 1-3-1-2-3-4, deve parar imediatamente de descer o caminho, pois é garantido que ele termina em decepção. Ainda seria possível calcular o número de mortes, com algumas contas matemáticas.
• Qualquer outra solução que troque memória por tempo ou permita evitar agressivamente as seguintes rotas sem saída. fiz isso também!

Algumas notas abstratas sobre uma solução

Se eu tiver tempo, vou converter isso em um algoritmo ...

Para um dado gráfico G, existe um sub-gráfico conectado G'que contém a cidade 1. Se houver uma solução infinito então existirá uma sub-gráfico conectado G''de G'que contém Vcidades e Pcaminhos.

Os caminhos Pde G''podem ser particionados de forma que {p}contenha um caminho que possua um custo mínimo de todos os caminhos Pe P/{p}sejam todos os outros caminhos (formando uma árvore de abrangência ou possivelmente um ciclo). Se assumirmos que pnão é uma borda circular (conectando as duas extremidades à mesma cidade), ela conectará duas cidades ( v1e v2) e custará cmunição, então você (o sobrevivente) poderá atravessar de um lado v1para o outro v2com um custo total de 2cmunição e isso aumentará a munição em todas as cidades em 2 (para um aumento total de 2|V|dentro G''- algumas das quais serão coletadas v1e v2).

Se você viajar de v1para v2e de volta para v1múltipla ( m) vezes e, em seguida, fazer uma viagem de v1ao longo das bordas P/{p}para visitar todas as outras que cidades v1e v2antes de retornar ao v1e isso leva ncaminhos para alcançar (onde |P/{p}| ≤ n ≤ 2|P/{p}|já que você nunca precisará percorrer um caminho mais duas vezes) com um custo de ke as cidades ganharão 2m|V|munição (novamente algumas das quais serão coletadas durante a travessia).

Dado tudo isso, você pode saber se uma solução infinita é potencialmente possível se o custo k + 2mcfor igual ou menor que a recompensa total 2(m+n)|V|.

Há uma complexidade adicional para o problema:

• pode ser necessário viajar da cidade inicial 1para {p}a primeira iteração e considerar esse custo; e
• você também precisa garantir que o nível me nseja baixo o suficiente para não ficar sem munição antes de poder passar pela primeira iteração, pois a primeira iteração terá um custo mais alto do que as iterações subseqüentes).

Isso leva a uma solução neutra em termos de custo de 24 caminhos para o exemplo da pergunta (os números são as cidades visitadas):

1,3,1,3,1,3,1,3,1,3,1,3,1,3,1,3,1,3,2,4,2,5,2,3, ... and repeat ...