Cod sursa(job #2100087)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 5 ianuarie 2018 10:25:57
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <bits/stdc++.h>

using namespace std;

const int INF = (int) 1e9;
const int MAXN = 301;

vector <int> g[MAXN + 1];

int cap[MAXN + 1][MAXN + 1];
int flx[MAXN + 1][MAXN + 1];

inline void addEdge(int x, int y, int c) {
    cap[x][y] = c;
    g[x].push_back(y);
    g[y].push_back(x);
}

int from[MAXN + 1], q[MAXN + 1];
bool viz[MAXN + 1];

inline bool bfs(int s, int d) {
    memset(viz, 0, sizeof(viz));
    int b = 0, e = 0;
    q[e++] = s;
    viz[s] = 1;
    while(b < e) {
        int nod = q[b];
        for(auto it : g[nod]) {
            if(cap[nod][it] > flx[nod][it] && viz[it] == 0) {
                q[e++] = it;
                from[it] = nod;
                viz[it] = 1;
            }
         }
         b++;
    }
    return viz[d];
}

vector < pair <int, int> > sol;

int main() {
    ifstream cin("harta.in");
    ofstream cout("harta.out");
    int i, j, n, x, y;
    ios::sync_with_stdio(false);
    cin >> n;
    int s = 0, d = 3 * n + 1;
    for(i = 1; i <= n; i++) {
        cin >> x >> y;
        addEdge(s, i, INF);
        addEdge(i, i + n, x);
        for(j = 1; j <= n; j++) {
            if(j != i)
                addEdge(i + n, j + 2 * n, 1);
        }
        addEdge(i + 2 * n, d, y);
    }
    while(bfs(s, d)) {
        int nod = d;
        int mn = INF;
        while(nod != s) {
            mn = min(mn, cap[from[nod]][nod] - flx[from[nod]][nod]);
            nod = from[nod];
        }
        nod = d;
        while(nod != s) {
            flx[from[nod]][nod] += mn;
            flx[nod][from[nod]] -= mn;
            nod = from[nod];
        }
    }
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            int val = flx[i + n][j + 2 * n];
            while(val > 0) {
                val--;
                sol.push_back({i, j});
            }
        }
    }
    cout << sol.size() << "\n";
    for(auto it : sol) {
        cout << it.first << " " << it.second << "\n";
    }
    return 0;
}