Cod sursa(job #1973104)

Utilizator KusikaPasa Corneliu Kusika Data 24 aprilie 2017 14:38:50
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;

//MACROS
#define pb push_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
typedef long long LL;
typedef pair <int,int> PII;

int w[222][222], cap[222][222];
int n, m, t, s;
bool vis[222];

bool dive(int u) {
    if (u == s) return true;
    vis[u] = true;
    rep(v,1,s+1) {
        if (vis[v] || w[u][v] >= cap[u][v]) continue;
        if (dive(v)) {
            w[u][v]++;
            w[v][u]--;
            return true;
        }
    }
    return false;
}

int main() {
	freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
	cin >> n;
	t = 0, s = 2*n+1;
	rep(i,1,n+1) {
	    int in, out;
        cin >> out >> in;
        cap[t][i] = out;
        cap[i+n][s] = in;
        m += in;
	}

	rep(i,1,n+1) rep(j,n+1,s) if (i + n != j) cap[i][j] = 1;

	rep(i,0,m) {
        rep(j,0,s+1) vis[j] = false;
        dive(t);
	}
	cout << m << "\n";
	rep(i,1,n+1) rep(j,n+1,s) if (w[i][j] > 0) cout << i << " " << j-n << "\n";
}