Cod sursa(job #2513562)

Utilizator daniel.grosuDaniel Grosu daniel.grosu Data 23 decembrie 2019 13:45:46
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <iostream>
#include <list>
#include <cstring>
#include <unordered_map>
#include <numeric>
#include <cassert>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <iomanip>

using namespace std;
typedef long long LL;
typedef long double LD;
const int inf = 2*(1e9);
const long long infl = 2*(1e18) + 10;
const long long MOD = 998244853;
const int NMAX = 500;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, -1, 0, 1};



int C[NMAX][NMAX];
int F[NMAX][NMAX];
vector<int> G[NMAX];
int p[NMAX];
bool viz[NMAX];
int N,M,flow,x,y,z,minf;

queue<int> q;

bool bfs()
{
    q.push(1);
    memset(viz, 0, sizeof(viz));
    viz[1]=1;

    while(!q.empty())
    {
        int curr=q.front(); q.pop();

        if(curr==N)
            continue;
        for(int i=0; i<G[curr].size(); ++i)
        {
            int v=G[curr][i];
            if(C[curr][v] == F[curr][v] || viz[v])
                continue;
            viz[v]=true;
            q.push(v);
            p[v]=curr;
        }
    }
    return viz[N];
}

int outdegree[NMAX];
int indegree[NMAX];

void solve()
{
    int n;
    cin>>n;

    for(int i = 1; i <= n; ++i){
        cin>>outdegree[i]>>indegree[i];
    }

    N = 2*n + 2;


    for(int i = 1; i <= n; ++i){
            C[1][1 + i] = outdegree[i];
            G[1].push_back(1 + i);
            G[1 + i].push_back(1);
            C[1 + i + n][N] = indegree[i];
            G[1 + i + n].push_back(N);
            G[N].push_back(1 + i + n);
    }


    for(int i = 1; i <= n; ++i){
        for(int j = i+1; j <= n; ++j){
            C[1 + i][1 + j + n] = 1;
            G[1 + i].push_back(1 + j + n);
            G[1 + j + n].push_back(1 + i);
            C[1 + j][1 + i + n] = 1;
            G[1 + j].push_back(1 + i + n);
            G[1 + i + n].push_back(1 + j);
        }
    }

    flow = 0;
    bfs();

    while(bfs())
    {
        for(int i=0; i < G[N].size(); ++i)
        {
            int curr = G[N][i];
            if(C[curr][N] == F[curr][N] || !viz[curr])
                continue;
            minf = 0xffffff;
            p[N]=curr;
            for(int i=N; i!=1; i=p[i])
                minf=min(minf, C[p[i]][i]-F[p[i]][i]);

            if(minf==0)
                continue;
            for(int i=N; i!=1; i=p[i])
            {
                F[p[i]][i]+=minf;
                F[i][p[i]]-=minf;
            }
            flow+=minf;
        }
    }

    vector<pair<int, int>> edges;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if(i != j){
                if(F[1 + i][1 + j + n] == 1){
                    edges.push_back({i, j});
                }
            }
        }
    }
    cout<<edges.size()<<"\n";
    for(auto p: edges){
        cout<<p.first<<" "<<p.second<<"\n";
    }
    //cout<<flow<<"\n";

}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout << setprecision(16) << fixed;

    assert(freopen("harta.in", "rt", stdin));
    assert(freopen("harta.out", "wt", stdout));

    solve();

    return 0;
}