Cod sursa(job #1980207)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 12 mai 2017 16:03:04
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int NMAX = 205;
int N,c[NMAX][NMAX],f[NMAX][NMAX],pr[NMAX],viz[NMAX],M;
vector<int> v[NMAX],sol[NMAX];

void citire()
{

    in>>N;
    int x,y;
    for(int i = 1 ; i <= N ; ++i){
        in>>x>>y;
        c[0][i] += x;
        c[N+i][2*N+1] += y;
        v[0].push_back(i);
        v[i].push_back(0);
        v[N+i].push_back(2*N+1);
        v[2*N+1].push_back(N+i);
    }
    for(int i = 1 ; i <= N ; ++i)
        for(int j = 1 ; j <= N ; ++j)
            if(i != j){
                c[i][N+j] += 1;
                v[i].push_back(N+j);
                v[N+j].push_back(i);
            }
    in.close();
}

void reset()
{

    for(int i = 0 ; i <= 2*N + 1 ; ++i)
        viz[i] = 0;
}

int bfs()
{

    reset();
    viz[0] = 1;
    queue<int> Q;
    Q.push(0);
    while(!Q.empty())
    {

        int virf = Q.front();
        Q.pop();
        for(int i = 0 ; i < v[virf].size() ; ++i){
            int now = v[virf][i];
            if(viz[now] || c[virf][now] == f[virf][now])
                continue;
            viz[now] = 1;
            pr[now] = virf;
            Q.push(now);
        }
    }
    return viz[2*N + 1];
}

void max_flow()
{

    while(bfs()){

        for(int i = 0 ; i < v[2*N + 1].size() ; ++i){

            if(!viz[v[2*N+1][i]] || c[v[2*N+1][i]][2*N+1] == f[v[2*N+1][i]][2*N+1])
                continue;
            pr[2*N+1] = v[2*N+1][i];
            int minim = 1 << 30;
            for(int act = 2*N + 1 ; act != 0 ; act = pr[act])
                minim = min(minim,c[pr[act]][act] - f[pr[act]][act]);
            for(int act = 2*N + 1 ; act != 0 ; act = pr[act]){
                f[pr[act]][act] += minim;
                f[act][pr[act]] -= minim;
            }
        }
    }
    for(int i = 1 ; i <= N ; ++i)
        for(int j = 1 ; j <= N ; ++j)
            if(i != j && f[i][N+j])
                sol[i].push_back(j),++M;
}

void write()
{

    out<<M<<"\n";
    for(int i = 1 ; i <= N ; ++i)
        for(int j = 0 ; j < sol[i].size() ; ++j)
            out<<i<<" "<<sol[i][j]<<"\n";
    out.close();
}

int main()
{

    citire();
    max_flow();
    write();
    return 0;
}