Cod sursa(job #3336807)

Utilizator diana_dd03Dorneanu Diana diana_dd03 Data 25 ianuarie 2026 23:29:18
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m, e, N;
vector<vector<int>>Adj;
vector<vector<int>>Adj_rev;
vector<vector<long>>flow;
vector<vector<long>>capacity;
vector<int>parent;
vector<int>vis;
vector<int>din;
vector<int>dout;

bool bfs(int s, int t) {
    parent.assign(N, 0);
    vis.assign(N, 0);

    queue<int>q;
    q.push(s);
    vis[s]=1;
    while (!q.empty()) {
        int u=q.front();
        q.pop();
        for (int &v:Adj[u]) {
            if (vis[v]==0 && capacity[u][v] - flow[u][v] > 0 ) {
                parent[v]=u;
                if (v == t)
                    return 1;
                q.push(v);
                vis[v]=1;
            }
        }
        for (int& v:Adj_rev[u]) {
            if (vis[v]==0 && flow[v][u] > 0 ) {
                parent[v]=-u;
                if (v == t)
                    return 1;
                q.push(v);
                vis[v]=1;
            }
        }
    }
    return 0;
}

long EdmondsKarp(int s, int t) {
    long maxflow=0;

    while (bfs(s, t)) {
        int node = t;
        long ip = LONG_MAX;
        while (node!=s) {
            if (parent[node] > 0) {
                ip = min(ip, capacity[parent[node]][node] - flow[parent[node]][node]);
                node=parent[node];
            }
            else {
                ip = min(ip, flow[node][-parent[node]]);
                node=-parent[node];
            }
        }
        node = t;
        while (node!=s) {
            if (parent[node] > 0) {
                flow[parent[node]][node] += ip;
                node=parent[node];
            }
            else {
                flow[node][-parent[node]]-=ip;
                node=-parent[node];
            }
        }
        maxflow+=ip;
    }
    return maxflow;
}

int main() {
    fin>>n;
    N=n+n+3;
    Adj.resize(N);
    Adj_rev.resize(N);
    flow.resize(N);
    capacity.resize(N);
    din.assign(n+1, 0);
    dout.assign(n+1, 0);

    for (int i=0;i<=n+n+2;i++) {
        flow[i].assign(N, 0);
        capacity[i].assign(N, 0);
    }

    for (int i=1;i<=n;i++)
        fin>>dout[i]>>din[i];

    int s=n+n+1, t=n+n+2;
    for (int i=1;i<=n;i++) {
        Adj[s].push_back(i);
        Adj_rev[i].push_back(s);
        capacity[s][i] = dout[i];
    }
    for (int i=n+1;i<=n+n;i++){
        Adj[i].push_back(t);
        Adj_rev[t].push_back(i);
        capacity[i][t] = din[i-n];
    }
    for (int i=1;i<=n;i++)
        for (int j=n+1;j<=n+n;j++) {
            if (j - n == i) continue;
            Adj[i].push_back(j);
            Adj_rev[j].push_back(i);
            capacity[i][j]=1;
        }
    int nr_drumuri=EdmondsKarp(s, t);
    fout<<nr_drumuri<<'\n';
    for (int nod1 = 1; nod1 <= n; nod1++) {
        for (int nod2 = n+1; nod2 <= 2*n; nod2++) {
            if (flow[nod1][nod2] == 1) {
                fout << nod1 << " " << (nod2 - n) << "\n";
            }
        }
    }




    return 0;
}