Cod sursa(job #2596499)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 9 aprilie 2020 19:41:09
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 100;
const int INF = 2.e9;
int cf[2 * NMAX + 5][2 * NMAX + 5] , viz[2 * NMAX + 5] , n , s , t;
int bfs()
{
    memset(viz , -1 , sizeof(viz));
    viz[s] = -2;
    int u , v;
    queue <int> q;
    q.push(s);
    while(!q.empty())
    {
        u = q.front();
        q.pop();
        if(u == t)
            continue;
        for(v = 0 ; v <= t ; v ++)
            if(viz[v] == -1 && cf[u][v] > 0)
            {
                viz[v] = u;
                q.push(v);
            }
    }
    if(viz[t] == -1)
        return 0;
    return 1;
}
void update_flow()
{
    int nod , flow;
    flow = INF;
    for(nod = t ; viz[nod] != -2 ; nod = viz[nod])
        flow = min(flow , cf[viz[nod]][nod]);
    for(nod = t ; viz[nod] != -2 ; nod = viz[nod])
    {
        cf[viz[nod]][nod] = cf[viz[nod]][nod] - flow;
        cf[nod][viz[nod]] = cf[nod][viz[nod]] + flow;
    }
}
void max_flow()
{
    int nod;
    while(bfs())
        for(nod = n + 1 ; nod <= 2 * n ; nod ++)
        {
            if(viz[nod] == -1 || cf[nod][t] == 0)
                continue;
            viz[t] = nod;
            update_flow();
        }
}
int main()
{
    freopen("harta.in" , "r" , stdin);
    freopen("harta.out" , "w" , stdout);
    int i , j , m , x , y;
    scanf("%d" , &n);
    m = 0;
    t = 2 * n + 1;
    for(i = 1 ; i <= n ; i ++)
    {
        scanf("%d%d" , &x , &y);
        cf[s][i] = x;
        cf[n + i][t] = y;
        m = m + x;
    }
    for(i = 1 ; i <= n ; i ++)
        for(j = 1 ; j <= n ; j ++)
            if(i != j)
                cf[i][n + j] = 1;
    s = 0;
    max_flow();
    printf("%d\n" , m);
    for(i = 1 ; i <= n ; i ++)
        for(j = 1 ; j <= n ; j ++)
            if(i != j && cf[i][n + j] == 0)
                printf("%d %d\n" , i , j);
    return 0;
}