Cod sursa(job #2216878)

Utilizator Constantin.Dragancea Constantin Constantin. Data 28 iunie 2018 11:44:21
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
int n, s, t, pr[210], c[210][210];
pair <int, int> a[110];
vector <int> v[210];
vector <pair <int,int> > sol;
bool viz[210];
queue <int> Q;

bool bfs(){
    for (int i=0; i<=t; i++) viz[i] = 0;
    Q.push(s);
    viz[s] = 1;
    while (!Q.empty()){
        int nod = Q.front();
        Q.pop();
        if (nod == t) continue;
        for (auto it: v[nod]){
            if (viz[it] || !c[nod][it]) continue;
            pr[it] = nod;
            viz[it] = 1;
            Q.push(it);
        }
    }
    return viz[t];
}

int main(){
    ifstream cin ("harta.in");
    ofstream cout ("harta.out");
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i].fi >> a[i].se;
    s = 0; t = 2*n + 1;
    for (int i=1; i<=n; i++){
        v[s].push_back(i);
        v[i].push_back(s);
        v[n+i].push_back(t);
        v[t].push_back(n+i);
        c[s][i] += a[i].fi;
        c[n+i][t] += a[i].se;
        for (int j=1; j<=n; j++){
            if (i == j) continue;
            v[i].push_back(j+n);
            v[j+n].push_back(i);
            c[i][j+n]++;
        }
    }
    while (bfs()){
        for (auto it: v[t]){
            if (!viz[it] || !c[it][t]) continue;
            pr[t] = it;
            bool flag = 1;
            for (int nod = t; nod != s && flag; nod = pr[nod])
                if (!c[pr[nod]][nod]) flag = 0;
            for (int nod = t; nod != s && flag; nod = pr[nod]){
                c[pr[nod]][nod]--;
                c[nod][pr[nod]]++;
            }
        }
    }
    for (int i=1; i<=n; i++){
        for (auto it: v[i]){
            if (it != s && !c[i][it]) sol.push_back({i, it-n});
        }
    }
    cout << sol.size() << "\n";
    for (auto it: sol) cout << it.fi << " " << it.se << "\n";
    return 0;
}