https://discopal.ispras.ru/index.php?action=history&feed=atom&title=Hardprob%2FMaximum_Integral_K-Multicommodity_Flow_On_Trees
Hardprob/Maximum Integral K-Multicommodity Flow On Trees - История изменений
2026-05-07T19:11:26Z
История изменений этой страницы в вики
MediaWiki 1.26.4
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Integral_K-Multicommodity_Flow_On_Trees&diff=25334&oldid=prev
StasFomin: Массовая правка: замена PCRE <m>\((\w)_(\w)\s*,\s*(\w)_(\w)\)</m> на <em>(\1<sub>\2</sub>, \3<sub>\4</sub>)</em>
2023-04-17T23:09:57Z
<p>Массовая правка: замена PCRE <m>\((\w)_(\w)\s*,\s*(\w)_(\w)\)</m> на <em>(\1<sub>\2</sub>, \3<sub>\4</sub>)</em></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 23:09, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <em>T=(V,E)</em>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em> пар вершин <<del class="diffchange diffchange-inline">m</del>>(<del class="diffchange diffchange-inline">s_i</del>,<del class="diffchange diffchange-inline">t_i</del>)</<del class="diffchange diffchange-inline">m</del>>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <em>T=(V,E)</em>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em> пар вершин <<ins class="diffchange diffchange-inline">em</ins>>(<ins class="diffchange diffchange-inline">s<sub>i</sub></ins>, <ins class="diffchange diffchange-inline">t<sub>i</sub></ins>)</<ins class="diffchange diffchange-inline">em</ins>>.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i ∈  N</m>, для каждой пары <<del class="diffchange diffchange-inline">m</del>>(<del class="diffchange diffchange-inline">s_i</del>,<del class="diffchange diffchange-inline">t_i</del>)</<del class="diffchange diffchange-inline">m</del>>, такой что <m>∀ e∈  E,\ \sum_{i=1}^k f_iq_i(e) ≤ c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <em>s<sub>i</sub></em> в <em>t<sub>i</sub></em>, и 0 в противном случае.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i ∈  N</m>, для каждой пары <<ins class="diffchange diffchange-inline">em</ins>>(<ins class="diffchange diffchange-inline">s<sub>i</sub></ins>, <ins class="diffchange diffchange-inline">t<sub>i</sub></ins>)</<ins class="diffchange diffchange-inline">em</ins>>, такой что <m>∀ e∈  E,\ \sum_{i=1}^k f_iq_i(e) ≤ c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <em>s<sub>i</sub></em> в <em>t<sub>i</sub></em>, и 0 в противном случае.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать сумму потоков <m>\sum_{i=1}^k f_i</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать сумму потоков <m>\sum_{i=1}^k f_i</m></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Integral_K-Multicommodity_Flow_On_Trees&diff=25220&oldid=prev
StasFomin: Массовая правка: замена PCRE <m>(\w)_(\w)</m> на <em>\1<sub>\2</sub></em>
2023-04-17T22:33:36Z
<p>Массовая правка: замена PCRE <m>(\w)_(\w)</m> на <em>\1<sub>\2</sub></em></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 22:33, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <em>T=(V,E)</em>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em> пар вершин <m>(s_i,t_i)</m>.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <em>T=(V,E)</em>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em> пар вершин <m>(s_i,t_i)</m>.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i ∈  N</m>, для каждой пары <m>(s_i,t_i)</m>, такой что <m>∀ e∈  E,\ \sum_{i=1}^k f_iq_i(e) ≤ c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <<del class="diffchange diffchange-inline">m</del>><del class="diffchange diffchange-inline">s_i</del></<del class="diffchange diffchange-inline">m</del>> в <<del class="diffchange diffchange-inline">m</del>><del class="diffchange diffchange-inline">t_i</del></<del class="diffchange diffchange-inline">m</del>>, и 0 в противном случае.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i ∈  N</m>, для каждой пары <m>(s_i,t_i)</m>, такой что <m>∀ e∈  E,\ \sum_{i=1}^k f_iq_i(e) ≤ c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <<ins class="diffchange diffchange-inline">em</ins>><ins class="diffchange diffchange-inline">s<sub>i</ins></<ins class="diffchange diffchange-inline">sub></em</ins>> в <<ins class="diffchange diffchange-inline">em>t<sub>i</sub</ins>></<ins class="diffchange diffchange-inline">em</ins>>, и 0 в противном случае.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать сумму потоков <m>\sum_{i=1}^k f_i</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать сумму потоков <m>\sum_{i=1}^k f_i</m></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Integral_K-Multicommodity_Flow_On_Trees&diff=25066&oldid=prev
StasFomin: Массовая правка: замена \leq на ≤
2023-04-17T21:26:11Z
<p>Массовая правка: замена \leq на ≤</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 21:26, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <em>T=(V,E)</em>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em> пар вершин <m>(s_i,t_i)</m>.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <em>T=(V,E)</em>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em> пар вершин <m>(s_i,t_i)</m>.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i ∈  N</m>, для каждой пары <m>(s_i,t_i)</m>, такой что <m>∀ e∈  E,\ \sum_{i=1}^k f_iq_i(e) <del class="diffchange diffchange-inline">\leq </del>c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <m>s_i</m> в <m>t_i</m>, и 0 в противном случае.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i ∈  N</m>, для каждой пары <m>(s_i,t_i)</m>, такой что <m>∀ e∈  E,\ \sum_{i=1}^k f_iq_i(e) <ins class="diffchange diffchange-inline">≤ </ins>c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <m>s_i</m> в <m>t_i</m>, и 0 в противном случае.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать сумму потоков <m>\sum_{i=1}^k f_i</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать сумму потоков <m>\sum_{i=1}^k f_i</m></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Integral_K-Multicommodity_Flow_On_Trees&diff=24952&oldid=prev
StasFomin: Массовая правка: замена \in на ∈
2023-04-17T18:00:24Z
<p>Массовая правка: замена \in на ∈</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 18:00, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <em>T=(V,E)</em>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em> пар вершин <m>(s_i,t_i)</m>.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <em>T=(V,E)</em>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em> пар вершин <m>(s_i,t_i)</m>.</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i <del class="diffchange diffchange-inline">\in </del>N</m>, для каждой пары <m>(s_i,t_i)</m>, такой что <m>∀ <del class="diffchange diffchange-inline">e\in </del>E,\ \sum_{i=1}^k f_iq_i(e) \leq c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <m>s_i</m> в <m>t_i</m>, и 0 в противном случае.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i <ins class="diffchange diffchange-inline">∈  </ins>N</m>, для каждой пары <m>(s_i,t_i)</m>, такой что <m>∀ <ins class="diffchange diffchange-inline">e∈  </ins>E,\ \sum_{i=1}^k f_iq_i(e) \leq c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <m>s_i</m> в <m>t_i</m>, и 0 в противном случае.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать сумму потоков <m>\sum_{i=1}^k f_i</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать сумму потоков <m>\sum_{i=1}^k f_i</m></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<!-- diff cache key discopal:diff:version:1.11a:oldid:24751:newid:24952 -->
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Integral_K-Multicommodity_Flow_On_Trees&diff=24751&oldid=prev
StasFomin: Массовая правка: замена <m>T=\left(V,E\right)</m> на <em>T=(V,E)</em>
2023-04-17T06:35:11Z
<p>Массовая правка: замена <m>T=\left(V,E\right)</m> на <em>T=(V,E)</em></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 06:35, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <<del class="diffchange diffchange-inline">m</del>>T=<del class="diffchange diffchange-inline">\left</del>(V,E<del class="diffchange diffchange-inline">\right</del>)</<del class="diffchange diffchange-inline">m</del>>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em> пар вершин <m>(s_i,t_i)</m>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <<ins class="diffchange diffchange-inline">em</ins>>T=(V,E)</<ins class="diffchange diffchange-inline">em</ins>>, пропускная способность на ребрах <em>c: E → N</em>, <em>k</em> пар вершин <m>(s_i,t_i)</m>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i \in N</m>, для каждой пары <m>(s_i,t_i)</m>, такой что <m>∀ e\in E,\ \sum_{i=1}^k f_iq_i(e) \leq c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <m>s_i</m> в <m>t_i</m>, и 0 в противном случае.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i \in N</m>, для каждой пары <m>(s_i,t_i)</m>, такой что <m>∀ e\in E,\ \sum_{i=1}^k f_iq_i(e) \leq c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <m>s_i</m> в <m>t_i</m>, и 0 в противном случае.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать сумму потоков <m>\sum_{i=1}^k f_i</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать сумму потоков <m>\sum_{i=1}^k f_i</m></div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Integral_K-Multicommodity_Flow_On_Trees&diff=24747&oldid=prev
StasFomin: Массовая правка: замена <m>c:E \rightarrow N</m> на <em>c: E → N</em>
2023-04-17T06:34:05Z
<p>Массовая правка: замена <m>c:E \rightarrow N</m> на <em>c: E → N</em></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 06:34, 17 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <m>T=\left(V,E\right)</m>, пропускная способность на ребрах <<del class="diffchange diffchange-inline">m</del>>c:E <del class="diffchange diffchange-inline">\rightarrow </del>N</<del class="diffchange diffchange-inline">m</del>>, <em>k</em> пар вершин <m>(s_i,t_i)</m>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <m>T=\left(V,E\right)</m>, пропускная способность на ребрах <<ins class="diffchange diffchange-inline">em</ins>>c: E <ins class="diffchange diffchange-inline">→ </ins>N</<ins class="diffchange diffchange-inline">em</ins>>, <em>k</em> пар вершин <m>(s_i,t_i)</m>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i \in N</m>, для каждой пары <m>(s_i,t_i)</m>, такой что <m>∀ e\in E,\ \sum_{i=1}^k f_iq_i(e) \leq c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <m>s_i</m> в <m>t_i</m>, и 0 в противном случае.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i \in N</m>, для каждой пары <m>(s_i,t_i)</m>, такой что <m>∀ e\in E,\ \sum_{i=1}^k f_iq_i(e) \leq c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <m>s_i</m> в <m>t_i</m>, и 0 в противном случае.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать сумму потоков <m>\sum_{i=1}^k f_i</m></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Максимизировать сумму потоков <m>\sum_{i=1}^k f_i</m></div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Integral_K-Multicommodity_Flow_On_Trees&diff=23501&oldid=prev
StasFomin: Массовая правка: замена {{hard-problem-on-lab17|{{PAGENAME}}}} на {{hard-problem-on-lab17|{{PAGENAME}}}}
<!-- * {{has-testdata-and-visualization}} -->
<!-- * {{has-pyomo-model}} -->
<!-- * {{has-npc-reduction}} -->
<!-- * {{add-random-fuzzing-tests}} -->
2023-04-10T20:45:27Z
<p>Массовая правка: замена {{hard-problem-on-lab17|{{PAGENAME}}}} на {{hard-problem-on-lab17|{{PAGENAME}}}} <!-- * {{has-testdata-and-visualization}} --> <!-- * {{has-pyomo-model}} --> <!-- * {{has-npc-reduction}} --> <!-- * {{add-random-fuzzing-tests}} --></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 20:45, 10 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l6" >Строка 6:</td>
<td colspan="2" class="diff-lineno">Строка 6:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{{hard-problem-on-lab17|{{PAGENAME}}}}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>{{hard-problem-on-lab17|{{PAGENAME}}}}</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><!-- * {{has-testdata-and-visualization}} --></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><!-- * {{has-pyomo-model}} --></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><!-- * {{has-npc-reduction}} --></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"><!-- * {{add-random-fuzzing-tests}} --></ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>----</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><small></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><small></div></td></tr>
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Integral_K-Multicommodity_Flow_On_Trees&diff=23363&oldid=prev
StasFomin: Массовая правка: замена <!-- start --> на <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
2023-04-10T19:59:09Z
<p>Массовая правка: замена <!-- start --> на <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;' lang='ru'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 19:59, 10 апреля 2023</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td>
<td colspan="2" class="diff-lineno">Строка 1:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><!-- start --></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><!-- start <ins class="diffchange diffchange-inline">--><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} </ins>--></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <m>T=\left(V,E\right)</m>, пропускная способность на ребрах <m>c:E \rightarrow N</m>, <em>k</em> пар вершин <m>(s_i,t_i)</m>.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Дерево <m>T=\left(V,E\right)</m>, пропускная способность на ребрах <m>c:E \rightarrow N</m>, <em>k</em> пар вершин <m>(s_i,t_i)</m>.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i \in N</m>, для каждой пары <m>(s_i,t_i)</m>, такой что <m>∀ e\in E,\ \sum_{i=1}^k f_iq_i(e) \leq c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <m>s_i</m> в <m>t_i</m>, и 0 в противном случае.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* Найти поток <m>f_i \in N</m>, для каждой пары <m>(s_i,t_i)</m>, такой что <m>∀ e\in E,\ \sum_{i=1}^k f_iq_i(e) \leq c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <m>s_i</m> в <m>t_i</m>, и 0 в противном случае.</div></td></tr>
<!-- diff cache key discopal:diff:version:1.11a:oldid:23301:newid:23363 -->
</table>
StasFomin
https://discopal.ispras.ru/index.php?title=Hardprob/Maximum_Integral_K-Multicommodity_Flow_On_Trees&diff=23301&oldid=prev
StasFomin: Новая страница: «<!-- start --> * Дерево <m>T=\left(V,E\right)</m>, пропускная способность на ребрах <m>c:E \rightarrow N</m>, <em>k</em> пар…»
2023-04-08T22:55:03Z
<p>Новая страница: «<!-- start --> * Дерево <m>T=\left(V,E\right)</m>, пропускная способность на ребрах <m>c:E \rightarrow N</m>, <em>k</em> пар…»</p>
<p><b>Новая страница</b></p><div><!-- start --><br />
* Дерево <m>T=\left(V,E\right)</m>, пропускная способность на ребрах <m>c:E \rightarrow N</m>, <em>k</em> пар вершин <m>(s_i,t_i)</m>.<br />
* Найти поток <m>f_i \in N</m>, для каждой пары <m>(s_i,t_i)</m>, такой что <m>∀ e\in E,\ \sum_{i=1}^k f_iq_i(e) \leq c(e)</m>, где <m>q_i(e)=1</m>, если <em>e</em> лежит на (единственном, тут дерево) пути из <m>s_i</m> в <m>t_i</m>, и 0 в противном случае.<br />
* Максимизировать сумму потоков <m>\sum_{i=1}^k f_i</m><br />
<br />
----<br />
{{hard-problem-on-lab17|{{PAGENAME}}}}<br />
----<br />
<small><br />
{{ViggoCode|node121}}<br />
<!-- {{GDCode|ND30}} --><br />
<!-- * [ Задача в википедии] --><br />
</small><br />
<!-- end --><br />
<br />
[[Категория:ClassicHardProblems]]</div>
StasFomin