Cod sursa(job #2960666)

Utilizator ScobiolaRaduScobiola Radu ScobiolaRadu Data 4 ianuarie 2023 20:02:19
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("harta.in");
ofstream out("harta.out");

int n, flow[201][201], tata[201], v[201][201];
bool viz[201];
vector<pair<int, int>> res;

vector<int> g[201];

bool bfs()
{
    int i;
    queue<int> q;

    for(i=1; i<=2 * n + 1; i++)
    {
        viz[i] = false;
        tata[i] = 0;
    }

    q.push(0);
    viz[0] = true;

    while(!q.empty())
    {
        int u = q.front();
        q.pop();

        for(auto i:g[u])
        {
            if(!viz[i] && v[u][i] > flow[u][i])
            {
                viz[i] = true;

                q.push(i);
                tata[i] = u;

                if(viz[2 * n + 1])
                    return true;
            }
        }

    }

    return viz[2 * n + 1];
}

int main()
{
    int i, j, x, y;
    in >> n;

    for(i = 1; i<= n; i++)
    {
        in>>x>>y;

        v[0][i] = x;
        v[i + n][2 * n + 1] = y;

        g[0].push_back(i);
        g[i].push_back(0);

        g[i + n].push_back(2 * n + 1);
        g[2 * n + 1].push_back(i + n);
    }

    for(i = 1; i <= n; i++)
        for(j = n+1; j <= 2 * n; j++)
            if(j - n != i)
            {
                v[i][j] = 1;
                g[i].push_back(j);
                g[j].push_back(i);
            }

    while(bfs())
        for(auto i : g[2 * n + 1])
        {
            int u = i;
            if(viz[u] && v[u][2 * n + 1] > flow[u][2 * n +1])
            {
                int mini = v[u][2 * n + 1] - flow[u][2 * n +1];

                while(u != 0)
                {
                    mini = min(mini, v[tata[u]][u] - flow[tata[u]][u]);
                    u = tata[u];
                }

                u = i;
                flow[u][2 * n + 1] += mini;
                flow[2 * n + 1][u] -= mini;

                while(u != 0)
                {
                    flow[tata[u]][u] += mini;
                    flow[u][tata[u]] -= mini;
                    u = tata[u];
                }
            }
        }

    for(i = 1; i <= n; i++)
        for(j = n+1; j<= 2 * n; j++)
            if(i + n != j && flow[i][j] == 1)
                res.push_back({i, j - n});

    out<<res.size()<<endl;
    for(auto i : res)
        out<<i.first<<" "<<i.second<<endl;

    return 0;
}