Введение

Вы одни на острове. Остальная часть человечества мертва ( вероятно, из-за ошибки в коде пользователя 12345 ). Пиратская Орда Зомби достигла вашего острова, и они бесконечны. Пришло время надрать задницу или жевать жевательную резинку, и вы все вышли из жвачки.

проблема

Наш сценарий конца света описывается двумя целыми числами в одной строке, mи n. На вашем острове расположены форпосты с уникальным номером от 1 до m. Следующие nстроки содержат каждые три целых числа, x, y, и z, разделенный пробел. xи yявляются уникальными идентификаторами двух аванпостов, а zтакже количеством зомби, которые встретятся на пути между ними.

Когда вы путешествуете по пути, вы теряете zбоеприпасы и убиваете zзомби. Если вы снова пойдете тем же путем, вы, к сожалению, встретите такое же количество зомби. Все аванпосты генерируют +1 боеприпасы каждый раз, когда вы путешествуете по пути. Вы начинаете с 100 боеприпасов на форпосте 1. Все форпосты начинаются с 0 патронов. Вы немедленно умрете, если не существует пути, для которого ваши боеприпасы превышают количество зомби на этом пути, а оставшаяся часть ваших боеприпасов превращается в убийства. Такова ваша последняя позиция.

Напишите программу, которая выводит максимальное количество зомби, которых вы можете убить для данного сценария. Если вы можете убить бесконечное количество зомби, просто вывод x.

Пример ввода

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

Пример вывода

x

Предположения

• Путь будет между двумя действующими аванпостами. То есть 1 <= x/ y<=m
• Если путь между xи yне указан, его нельзя пройти
• Путь двунаправленный
• 1 m<<= 100
• 1 n<<= 500
• Входные данные должны быть предоставлены через stdin, прочитаны из файла или приняты в качестве единственного аргумента программы, и они должны точно соответствовать формату примера
• Время выполнения вашей программы может быть сколь угодно большим, но оно должно быть определенно конечным

Код с наименьшим количеством символов выигрывает!

Ява ( менее гротескно: 8415 5291 3301)

Хорошо. В основном, я смущен, никто не представил решение. Поэтому несколько дней назад я начал пытаться решить эту проблему, потому что это здорово. , Перейдите по этой ссылке, чтобы посмотреть мой прогресс в этом через GitHub.

редактировать

Новая решающая версия, гораздо более «играемая в гольф», с исправленной проверкой цикла, идентифицированной MT0. Он также поддерживает быстрые маршруты переадресации, настраиваемые путем изменения объема памяти, доступного для виртуальной машины. Последнее БОЛЬШОЕ редактирование: понял, что у меня было несколько других мелких ошибок индекса и преждевременная оптимизация, что привело к неспособности рассмотреть довольно большое количество типов побед. Так что это исправлено, осторожно. Новая версия меньше и ниже. Для нашего эталонного маршрута, java -Xmx2GB ZombieHordeMinдовольно хорошо справляется с задачей (будьте осторожны, это займет некоторое время).

Классный фактоид

В увлекательном повороте есть МНОГИЕ решения на длину 24, и мой решатель находит одно отличное от MT0, но идентичное в принципе, за исключением того, что оно начинается с посещения других аванпостов, связанных с 1. Захватывающий! Полностью противостоит человеческой интуиции, но совершенно оправдан.

Основные решения

Так вот мой. Это (частично) игра в гольф, потому что это - экспоненциальный, почти грубый решатель силы. Я использую алгоритм IDDFS (поиск по глубине итеративного углубления вначале), так что это отличный общий решатель, который не пропускает, поэтому он решает обе части вопроса ОП, а именно:

• Если найден выигрышный маршрут (бесконечные зомби), выведите «x».
• Если все маршруты заканчиваются смертью (конечные зомби), выведите наибольшее количество убитых зомби.

Дайте ему достаточно энергии, памяти и времени, и он сделает это, даже карты с медленной смертью. Я потратил еще немного времени на улучшение этого решателя, и, хотя можно сделать еще больше, теперь это немного лучше. Я также интегрировал совет MT0 в отношении лучшего решения для бесконечных зомби и удалил несколько преждевременных оптимизаций из моего средства проверки win, что помешало предыдущей версии найти его, и теперь я действительно нахожу решение, очень похожее на описанное MT0.

Несколько других основных моментов:

• Как уже упоминалось, использует IDDFS, чтобы найти кратчайший возможный выигрышный маршрут.
• Поскольку он по сути своей DFS, он также обнаружит, заканчивается ли каждый маршрут смертью нашего героя, и отслеживает «лучший» маршрут с точки зрения большинства убитых зомби. Умри героем!
• Я описал алгоритм, чтобы сделать его более интересным для просмотра « Удалено» в целях игры в гольф. Перейдите по одной из ссылок на GitHub, чтобы увидеть версию ungolfed.
• Также есть множество комментариев, так что не стесняйтесь повторно реализовать свое собственное решение, основываясь на моем подходе, или покажите мне, как это должно быть сделано!
• Быстрая перемотка маршрута с учетом памяти
  • До доступной системной памяти будет отслеживать «конечные маршруты», которые не привели к смерти.
  • Используя причудливую процедуру сжатия и распаковки маршрутов, прогресс предыдущей итерации IDDFS восстанавливается, чтобы предотвратить повторное обнаружение всех ранее посещенных маршрутов.
  • В качестве преднамеренного побочного бонуса выступает в качестве тупикового маршрута. Маршруты тупиков не сохраняются и никогда не будут посещаться снова в будущих глубинах IDDFS.

История решателя

• Я попробовал несколько одностадийных алгоритмов упреждения, и хотя для очень простых сценариев они сработали, в конечном итоге они потерпели неудачу.
• Затем я попробовал двухшаговый алгоритм упреждения, который был .. неудовлетворительным.
• Затем я начал строить n-пошаговый прогноз, когда понял, что этот подход сводим к DFS, но DFS намного ... более элегантен.
• При создании DFS мне пришло в голову, что IDDFS обеспечит (а) поиск лучшего маршрута HERO (смерть) или (б) первый выигрышный цикл.
• Оказывается, создание программы проверки цикла выигрыша очень просто, но мне пришлось пройти несколько очень и очень неправильных итераций, прежде чем я получил доказуемо успешную программу проверки.
• Фактор win-path для MT0 убрал три линии преждевременной оптимизации, что сделало мой алгоритм слепым к нему.
• Добавлен адаптивный алгоритм кэширования маршрутов, который будет использовать всю предоставленную вами память для предотвращения ненужного повторного выполнения работы между вызовами IDDFS, а также отбрасывает тупиковые маршруты до пределов памяти.

(Гольф) код

Перейдем к коду (получите версию без загадки здесь или здесь ):

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

Получите код от github здесь, чтобы отслеживать любые изменения, которые я делаю. Вот некоторые другие карты, которые я использовал.

Пример вывода

Пример вывода для эталонного решения:

    $ 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

Прочитайте вывод маршрута следующим образом step:: source, route-to-get-here- ammo. Таким образом, в приведенном выше решении вы должны прочитать его как:

• На шаге 0, на заставе 1с боеприпасами 100.
• На шаге 1используйте маршрут, 1чтобы добраться до форпоста 3с боеприпасами97
• На шаге 2используйте маршрут, 1чтобы добраться до форпоста 1с боеприпасами95
• ...

Закрытие заметок

Итак, я надеюсь, что мое решение было труднее победить, но ПОЖАЛУЙСТА, ПОПРОБУЙТЕ! Используйте это против меня, добавьте параллельную обработку, улучшите теорию графов и т. Д. Пара вещей, которые я считаю, может улучшить этот подход:

• агрессивно «сокращать» циклы, чтобы исключить ненужное повторное чтение по мере продвижения алгоритма.
  • Пример: в примере задачи рассмотрите циклы 1-2-3 и другие перестановки как «один шаг», чтобы мы могли быстрее завершить цикл.
  • Например, если вы находитесь в узле 1, вы можете (а) перейти к 2, (б) перейти к 1, (в) пройти 1-2-3 в качестве одного шага и так далее. Это позволило бы решить сложить глубину в ширину, увеличивая количество маршрутов на определенной глубине, но значительно сокращая время решения для длинных циклов.
• убирать мертвые маршруты. Мое текущее решение не «помнит», что конкретный маршрут является тупиковым, и должно каждый раз открывать его заново. Было бы лучше отследить самый ранний момент на пути, в котором смерть неизбежна, и никогда не продвигаться дальше. сделал это...
• если вы будете осторожны, вы можете применить отбраковку мертвого маршрута как отбраковку под маршрута. Например, если 1-2-3-4 всегда приводит к смерти, и решатель собирается проверить маршрут 1-3-1-2-3-4, он должен немедленно прекратить спуск по этому пути, поскольку он гарантированно завершится. в разочаровании. Было бы все еще возможно вычислить количество убийств, с некоторой тщательной математикой.
• Любое другое решение, которое торгует памятью на время или позволяет агрессивно избегать тупиковых маршрутов. сделал это тоже!

Некоторые абстрактные заметки о решении

Если у меня будет время, я преобразую это в алгоритм ...

Для данного графа Gсуществует связный подграф, G'содержащий город 1. Если существует бесконечное решение , то будет существовать подключенный подграф G''из G'который содержит Vгорода и Pпуть.

Пути Pиз G''могут быть разделены таким образом, что{p} содержит путь , который имеет то минимальную стоимость всех путей в Pи P/{p}является всеми другими путями (образующие связующего дерева или , возможно , цикла). Если мы предположим, что pэто не петлевое ребро (соединяющее оба конца с одним и тем же городом), то оно соединит два города ( v1и v2) и будет стоить cбоеприпасов, тогда вы (выживший) сможете затем пересечь v1туда v2и обратно с общей стоимостью 2cбоеприпасов. и это увеличит боеприпасы во всех городах на 2 (для общего увеличения в 2|V|пределах G''- некоторые из которых будут собраны v1и v2).

Если вы путешествуете из v1 к v2и обратно v1несколько ( m) раз , а затем отправиться в путешествие из v1по краям , P/{p}чтобы посетить все , кроме городов v1и , v2прежде чем вернуться , v1и это займет nпути достижения (где , |P/{p}| ≤ n ≤ 2|P/{p}|так как вы никогда не должны пройти путь более чем в два раза) со стоимостью, kи города получат 2m|V|боеприпасы (опять же, некоторые из которых будут собраны во время обхода).

Учитывая все это, вы можете сказать, возможно ли бесконечное решение, если тогда стоимость k + 2mcравна или ниже, чем общее вознаграждение 2(m+n)|V|.

Существует дополнительная сложность проблемы в том, что:

• вам может понадобиться проехать от стартового города 1до {p}первой итерации, и вам необходимо учитывать эту стоимость; а также
• Вы также должны убедиться, что mи nдостаточно низки, чтобы у вас не кончились боеприпасы, прежде чем вы сможете сделать это через первую итерацию, поскольку первая итерация будет стоить дороже, чем последующие итерации).

Это приводит к 24 путям нейтрального по стоимости решения для примера в вопросе (цифры - количество посещенных городов):

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 ...