Cod sursa(job #3321439)

Utilizator stanciuvalentinStanciu-Tivlea Valentin Gabriel stanciuvalentin Data 9 noiembrie 2025 15:20:52
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,x,y,source,sink, flow[500][500],cap[500][500],dist[500];
vector <int> edges[500];
queue <int> q;

void add_edge(int x, int y, int c){
    edges[x].push_back(y);
    edges[y].push_back(x);
    cap[x][y]+=c;
}

bool bfs(int source, int destination){
    for(int i=source; i<=destination; i++)
        dist[i] = INT_MAX;
    dist[source] = 0;
    q.push(source);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(auto y:edges[x])
            if(dist[y] > dist[x]+1 and flow[x][y] < cap[x][y])
                dist[y] = dist[x]+1, q.push(y);
    }
    return dist[destination]!=INT_MAX;
}

int maxflow(int x, int sink, int maximumflow){
    if(x == sink)
        return maximumflow;
    if(maximumflow == 0)
        return 0;
    int totalflow = 0;
    for(auto y:edges[x])
        if(dist[y] == dist[x]+1)
        {
            int currentflow = maxflow(y, sink, min(maximumflow - totalflow, cap[x][y] - flow[x][y]));
            flow[x][y] += currentflow;
            flow[y][x] -= currentflow;
            totalflow += currentflow;
        }
    return totalflow;
}

int main()
{
    f>>n;
    source = 0, sink = n+n+1;
    for(int i=1; i<=n; i++)
    {
        f>>x>>y;
        add_edge(source, i, x);
        add_edge(n+i, sink, y);
        for(int j=1; j<=n; j++)
            if(i!=j)
                add_edge(i, n+j, 1);
    }
    int totalflow=0;
    while(bfs(source, sink))
        totalflow += maxflow(source, sink, INT_MAX);
    g<<totalflow<<'\n';
    for(int i=1; i<=n; i++)
        for(int j=n+1; j<=n+n; j++)
            if(flow[i][j]==1)
                g<<i<<' '<<j-n<<'\n';
    return 0;
}