Cod sursa(job #2416459)

Utilizator refugiatBoni Daniel Stefan refugiat Data 27 aprilie 2019 16:26:20
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <bits/stdc++.h>
using namespace std;
ifstream si("harta.in");
ofstream so("harta.out");

int n, dist[205], tata[205], cap[205][205];
vector<pair<int, int> > ans;
vector<int> v[205];
bool dijkstra() {
    memset(dist, 127, sizeof(dist));
    memset(tata, 0, sizeof(tata));
    queue<int>q;
    q.push(0);
    dist[0]=0;
    while(q.size()) {
        int x=q.front();
        q.pop();
        if(x==2*n+1)
            break;
        for(auto it:v[x])
            if(cap[x][it]) {
                if(dist[it]>dist[x]+1) {
                    dist[it]=dist[x]+1;
                    tata[it]=x;
                    q.push(it);
                }
            }
    }
    if(dist[2*n+1]>=1e9)
        return 0;
    int flx=1e9;
    for(int x=2*n+1; x; x=tata[x])
        flx=min(flx, cap[tata[x]][x]);
    for(int x=2*n+1; x; x=tata[x]) {
        cap[tata[x]][x]-=flx;
        cap[x][tata[x]]+=flx;
    }
    return 1;
}
int main()
{
    si>>n;
    for(int i=1; i<=n; ++i) {
        int a, b;
        si>>a>>b;
        v[0].push_back(i);
        v[i].push_back(0);
        cap[0][i]=a;
        v[i+n].push_back(2*n+1);
        v[2*n+1].push_back(i+n);
        cap[i+n][2*n+1]=b;
    }
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=n; ++j)
            if(i!=j) {
                v[i].push_back(j+n);
                v[j+n].push_back(i);
                cap[i][j+n]=1;
            }
    }
    while(dijkstra());
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=n; ++j) {
            if(i!=j)
                if(!cap[i][j+n])
                    ans.push_back({i,j});
        }
    }
    so<<ans.size()<<'\n';
    for(auto it:ans) {
        so<<it.first<<' '<<it.second<<'\n';
    }
    return 0;
}