Cod sursa(job #2961696)

Utilizator Eronatedudu zzz Eronate Data 6 ianuarie 2023 21:14:43
Problema Flux maxim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 14.72 kb
Raporteaza aceasta sursa 
<html>
<head>
<title>main.cpp</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css">
.s0 { color: #f9e2af; font-style: italic;}
.s1 { color: #cdd6f4;}
.s2 { color: #a6e3a1;}
.s3 { color: #cba6f7;}
.s4 { color: #cdd6f4;}
.s5 { color: #89dceb;}
.s6 { color: #fab387;}
.s7 { color: #585b70; font-style: italic;}
</style>
</head>
<body bgcolor="#1e1e2e">
<table CELLSPACING=0 CELLPADDING=5 COLS=1 WIDTH="100%" BGCOLOR="#606060" >
<tr><td><center>
<font face="Arial, Helvetica" color="#000000">
main.cpp</font>
</center></td></tr></table>
<pre><span class="s0">#include </span><span class="s2">&lt;bits/stdc++.h&gt;</span>
<span class="s3">using namespace </span><span class="s1">std</span><span class="s4">;</span>

<span class="s1">ifstream f</span><span class="s4">(</span><span class="s2">&quot;maxflow.in&quot;</span><span class="s4">);</span>
<span class="s1">ofstream g</span><span class="s4">(</span><span class="s2">&quot;maxflow.out&quot;</span><span class="s4">);</span>

<span class="s1">vector</span><span class="s5">&lt;</span><span class="s1">vector</span><span class="s5">&lt;</span><span class="s3">int</span><span class="s5">&gt;&gt; </span><span class="s1">gr</span><span class="s4">;</span>
<span class="s1">vector</span><span class="s5">&lt;</span><span class="s1">vector</span><span class="s5">&lt;</span><span class="s3">int</span><span class="s5">&gt;&gt; </span><span class="s1">flow</span><span class="s4">;</span>

<span class="s3">bool </span><span class="s1">bfs</span><span class="s4">(</span><span class="s3">int </span><span class="s1">n</span><span class="s4">, </span><span class="s3">int </span><span class="s1">src</span><span class="s4">, </span><span class="s3">int </span><span class="s1">dest</span><span class="s4">, </span><span class="s3">int </span><span class="s1">father</span><span class="s4">[])</span>
<span class="s4">{</span>
    <span class="s3">bool </span><span class="s1">visited</span><span class="s4">[</span><span class="s1">n</span><span class="s5">+</span><span class="s6">1</span><span class="s4">];</span>
    <span class="s1">memset</span><span class="s4">(</span><span class="s1">visited</span><span class="s4">, </span><span class="s6">0</span><span class="s4">, </span><span class="s3">sizeof</span><span class="s4">(</span><span class="s1">visited</span><span class="s4">));</span>
    <span class="s1">memset</span><span class="s4">(</span><span class="s1">father</span><span class="s4">, </span><span class="s6">0</span><span class="s4">, </span><span class="s3">sizeof</span><span class="s4">(</span><span class="s1">father</span><span class="s4">));</span>
    <span class="s1">queue</span><span class="s5">&lt;</span><span class="s3">int</span><span class="s5">&gt; </span><span class="s1">vertexes</span><span class="s4">;</span>
    <span class="s1">vertexes</span><span class="s4">.</span><span class="s1">push</span><span class="s4">(</span><span class="s1">src</span><span class="s4">);</span>

    <span class="s3">while</span><span class="s4">(</span><span class="s5">!</span><span class="s1">vertexes</span><span class="s4">.</span><span class="s1">empty</span><span class="s4">())</span>
    <span class="s4">{</span>
        <span class="s3">int </span><span class="s1">currentNode </span><span class="s5">= </span><span class="s1">vertexes</span><span class="s4">.</span><span class="s1">front</span><span class="s4">();</span>
        <span class="s1">vertexes</span><span class="s4">.</span><span class="s1">pop</span><span class="s4">();</span>
        <span class="s3">for</span><span class="s4">(</span><span class="s3">auto </span><span class="s1">extr2</span><span class="s5">: </span><span class="s1">gr</span><span class="s4">[</span><span class="s1">currentNode</span><span class="s4">])</span>
        <span class="s4">{</span>
            <span class="s3">if</span><span class="s4">(</span><span class="s1">extr2</span><span class="s5">!=</span><span class="s6">0</span><span class="s4">)</span>
            <span class="s3">if</span><span class="s4">(</span><span class="s5">!</span><span class="s1">visited</span><span class="s4">[</span><span class="s1">extr2</span><span class="s4">] </span><span class="s3">and </span><span class="s1">flow</span><span class="s4">[</span><span class="s1">currentNode</span><span class="s4">][</span><span class="s1">extr2</span><span class="s4">]</span><span class="s5">&gt;</span><span class="s6">0</span><span class="s4">) </span><span class="s7">//daca nu am vizitat nodul extr2</span>
                <span class="s7">//si capacitatea muchiei formata din nodul curent si extremitatea 2 permite trecerea flow-ului</span>
            <span class="s4">{</span>
                <span class="s1">father</span><span class="s4">[</span><span class="s1">extr2</span><span class="s4">] </span><span class="s5">= </span><span class="s1">currentNode</span><span class="s4">;</span>
                <span class="s3">if</span><span class="s4">(</span><span class="s1">extr2 </span><span class="s5">== </span><span class="s1">dest</span><span class="s4">)</span>
                    <span class="s3">return true</span><span class="s4">;</span>
                <span class="s1">vertexes</span><span class="s4">.</span><span class="s1">push</span><span class="s4">(</span><span class="s1">extr2</span><span class="s4">);</span>
                <span class="s1">visited</span><span class="s4">[</span><span class="s1">extr2</span><span class="s4">] </span><span class="s5">= </span><span class="s3">true</span><span class="s4">;</span>
            <span class="s4">}</span>
        <span class="s4">}</span>

    <span class="s4">}</span>
    <span class="s3">return false</span><span class="s4">; </span><span class="s7">//nu am gasit un drum de la sursa la destinatie, inseamna nu mai am drumuri si ca am ajuns la flux maxim</span>
<span class="s4">}</span>

<span class="s3">int </span><span class="s1">fordFulkerson</span><span class="s4">(</span><span class="s3">int </span><span class="s1">n</span><span class="s4">, </span><span class="s3">int </span><span class="s1">src</span><span class="s4">, </span><span class="s3">int </span><span class="s1">dest</span><span class="s4">)</span>
<span class="s4">{</span>
    <span class="s3">int </span><span class="s1">u</span><span class="s4">, </span><span class="s1">v</span><span class="s4">, </span><span class="s1">max_flow_for_route</span><span class="s4">, </span><span class="s1">currentNode</span><span class="s4">;</span>

    <span class="s3">int </span><span class="s1">father</span><span class="s4">[</span><span class="s1">n</span><span class="s5">+</span><span class="s6">1</span><span class="s4">];</span>
    <span class="s1">memset</span><span class="s4">(</span><span class="s1">father</span><span class="s4">, </span><span class="s6">0</span><span class="s4">, </span><span class="s3">sizeof</span><span class="s4">(</span><span class="s1">father</span><span class="s4">));</span>
    <span class="s3">int </span><span class="s1">srcAux </span><span class="s5">= </span><span class="s1">src</span><span class="s4">, </span><span class="s1">destAux </span><span class="s5">= </span><span class="s1">dest</span><span class="s4">, </span><span class="s1">fNode</span><span class="s4">, </span><span class="s1">finalFlow </span><span class="s5">= </span><span class="s6">0</span><span class="s4">;</span>

    <span class="s3">while</span><span class="s4">(</span><span class="s1">bfs</span><span class="s4">(</span><span class="s1">n</span><span class="s4">, </span><span class="s1">src</span><span class="s4">, </span><span class="s1">dest</span><span class="s4">, </span><span class="s1">father</span><span class="s4">))</span>
    <span class="s4">{</span>
        <span class="s1">max_flow_for_route </span><span class="s5">= </span><span class="s1">INT_MAX</span><span class="s4">;</span>
        <span class="s1">srcAux </span><span class="s5">= </span><span class="s1">src</span><span class="s4">;</span>
        <span class="s1">destAux </span><span class="s5">= </span><span class="s1">dest</span><span class="s4">;</span>
        <span class="s3">while</span><span class="s4">(</span><span class="s1">destAux</span><span class="s5">!=</span><span class="s1">srcAux</span><span class="s4">)</span>
        <span class="s4">{</span>
            <span class="s7">//calculez flow-ul maxim de transmis pe drumul gasit de bfs</span>
            <span class="s7">//g&lt;&lt;father[destAux]&lt;&lt;' '&lt;&lt;destAux&lt;&lt;&quot; &quot;&lt;&lt;flow[father[destAux]][destAux]&lt;&lt;endl;</span>
            <span class="s1">max_flow_for_route </span><span class="s5">= </span><span class="s1">min</span><span class="s4">(</span><span class="s1">max_flow_for_route</span><span class="s4">, </span><span class="s1">flow</span><span class="s4">[</span><span class="s1">father</span><span class="s4">[</span><span class="s1">destAux</span><span class="s4">]][</span><span class="s1">destAux</span><span class="s4">]);</span>
            <span class="s1">destAux </span><span class="s5">= </span><span class="s1">father</span><span class="s4">[</span><span class="s1">destAux</span><span class="s4">];</span>
        <span class="s4">}</span>
        <span class="s1">destAux </span><span class="s5">= </span><span class="s1">dest</span><span class="s4">;</span>
        <span class="s1">srcAux </span><span class="s5">= </span><span class="s1">src</span><span class="s4">;</span>
        <span class="s7">//acum updatez graful rezidual pe drumul gasit de bfs</span>
        <span class="s3">while</span><span class="s4">(</span><span class="s1">destAux</span><span class="s5">!=</span><span class="s1">srcAux</span><span class="s4">)</span>
        <span class="s4">{</span>
            <span class="s1">fNode </span><span class="s5">= </span><span class="s1">father</span><span class="s4">[</span><span class="s1">destAux</span><span class="s4">];</span>
            <span class="s1">flow</span><span class="s4">[</span><span class="s1">fNode</span><span class="s4">][</span><span class="s1">destAux</span><span class="s4">] </span><span class="s5">-= </span><span class="s1">max_flow_for_route</span><span class="s4">;    </span><span class="s7">//muchia mea pe directia corecta va avea o capacitate mai mica de flow</span>
            <span class="s1">flow</span><span class="s4">[</span><span class="s1">destAux</span><span class="s4">][</span><span class="s1">fNode</span><span class="s4">] </span><span class="s5">+= </span><span class="s1">max_flow_for_route</span><span class="s4">;    </span><span class="s7">//muchia pe directia inversa va avea mai mult flow de dat,</span>
            <span class="s7">//logic pt ca voi avea mai mult flow de extras</span>
            <span class="s1">destAux </span><span class="s5">= </span><span class="s1">fNode</span><span class="s4">;</span>
        <span class="s4">}</span>

        <span class="s1">finalFlow </span><span class="s5">+= </span><span class="s1">max_flow_for_route</span><span class="s4">; </span><span class="s7">//adun flow-ul drumului la flow-ul final</span>
    <span class="s4">}</span>
    <span class="s3">return </span><span class="s1">finalFlow</span><span class="s4">;</span>
<span class="s4">}</span>
<span class="s3">int </span><span class="s1">main</span><span class="s4">()</span>
<span class="s4">{</span>

    <span class="s3">int </span><span class="s1">n</span><span class="s4">,</span><span class="s1">m</span><span class="s4">,</span><span class="s1">node1</span><span class="s4">,</span><span class="s1">node2</span><span class="s4">,</span><span class="s1">flux</span><span class="s4">;</span>
    <span class="s1">f</span><span class="s5">&gt;&gt;</span><span class="s1">n</span><span class="s5">&gt;&gt;</span><span class="s1">m</span><span class="s4">;</span>
    <span class="s1">flow</span><span class="s4">.</span><span class="s1">resize</span><span class="s4">(</span><span class="s6">1001</span><span class="s4">);</span>
    <span class="s1">gr</span><span class="s4">.</span><span class="s1">resize</span><span class="s4">(</span><span class="s6">1001</span><span class="s4">);</span>
    <span class="s3">for</span><span class="s4">(</span><span class="s3">int </span><span class="s1">i</span><span class="s5">=</span><span class="s6">1</span><span class="s4">;</span><span class="s1">i</span><span class="s5">&lt;=</span><span class="s6">1001</span><span class="s4">;</span><span class="s1">i</span><span class="s5">++</span><span class="s4">)</span>
        <span class="s1">flow</span><span class="s4">[</span><span class="s1">i</span><span class="s4">].</span><span class="s1">resize</span><span class="s4">(</span><span class="s6">1001</span><span class="s4">);</span>
    <span class="s3">for</span><span class="s4">(</span><span class="s3">int </span><span class="s1">i</span><span class="s5">=</span><span class="s6">1</span><span class="s4">;</span><span class="s1">i</span><span class="s5">&lt;=</span><span class="s1">m</span><span class="s4">;</span><span class="s1">i</span><span class="s5">++</span><span class="s4">)</span>
    <span class="s4">{</span>
        <span class="s1">f</span><span class="s5">&gt;&gt;</span><span class="s1">node1</span><span class="s5">&gt;&gt;</span><span class="s1">node2</span><span class="s5">&gt;&gt;</span><span class="s1">flux</span><span class="s4">;</span>
        <span class="s1">gr</span><span class="s4">[</span><span class="s1">node1</span><span class="s4">].</span><span class="s1">push_back</span><span class="s4">(</span><span class="s1">node2</span><span class="s4">);</span>
        <span class="s1">gr</span><span class="s4">[</span><span class="s1">node2</span><span class="s4">].</span><span class="s1">push_back</span><span class="s4">(</span><span class="s1">node1</span><span class="s4">);</span>
        <span class="s1">flow</span><span class="s4">[</span><span class="s1">node1</span><span class="s4">][</span><span class="s1">node2</span><span class="s4">] </span><span class="s5">= </span><span class="s1">flux</span><span class="s4">;</span>
    <span class="s4">}</span>

<span class="s7">//    for(int i =1; i&lt;=n;i++)</span>
<span class="s7">//    {for(auto j: gr[i])</span>
<span class="s7">//            g&lt;&lt;j&lt;&lt;' ';</span>
<span class="s7">//        g&lt;&lt;endl;}</span>
<span class="s7">//    g&lt;&lt;endl;</span>
<span class="s7">//    for(int i =1; i&lt;=n;i++)</span>
<span class="s7">//        {for(auto j: flow[i])</span>
<span class="s7">//            g&lt;&lt;j&lt;&lt;' ';</span>
<span class="s7">//        g&lt;&lt;endl;}</span>

    <span class="s1">g</span><span class="s5">&lt;&lt;</span><span class="s1">fordFulkerson</span><span class="s4">(</span><span class="s1">n</span><span class="s4">,</span><span class="s6">1</span><span class="s4">,</span><span class="s1">n</span><span class="s4">);</span>
    <span class="s3">return </span><span class="s6">0</span><span class="s4">;</span>
<span class="s4">}</span>
</pre>
</body>
</html>