Cod sursa(job #1093347)

Utilizator assa98Andrei Stanciu assa98 Data 27 ianuarie 2014 21:54:58
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAX_N=110;

ifstream cin("harta.in");
ofstream cout("harta.out");

int gi[MAX_N];
int go[MAX_N];

int cap[2*MAX_N][2*MAX_N];
int flux[2*MAX_N][2*MAX_N];

vector<int> A[2*MAX_N];
int n;

bool viz[2*MAX_N];
int dad[2*MAX_N];

void graf(int N) {
    n=2*N+1;
    for(int i=1;i<=N;i++) {
        cap[0][i]=go[i];
        if(go[i]) {
            A[0].push_back(i);
            A[i].push_back(0);
        }
    }
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=N;j++) {
            if(i==j) {
                continue;
            }
            cap[i][j+N]=1;
            A[i].push_back(j+N);
            A[j+N].push_back(i);
        }
    }
    for(int i=1;i<=N;i++) {
        cap[i+N][n]=gi[i];
        if(gi[i]) {
            A[i+N].push_back(n);
            A[n].push_back(i+N);
        }
    }
}

bool bfs() {
    memset(viz,0,sizeof(viz));
    memset(dad,0,sizeof(dad));
    queue<int> Q;
    Q.push(0);
    viz[0]=true;
    while(!Q.empty()) {
        int nod=Q.front();
        Q.pop();
        for(auto it=A[nod].begin(); it!=A[nod].end(); it++) {
            if(!viz[*it]&&flux[nod][*it]<cap[nod][*it]) {
                Q.push(*it);
                //printf("%d\n",*it);
                viz[*it]=true;
                dad[*it]=nod;
            }
        }
    }
    return viz[n];
}

int maxflow() {
    
    int fluxmax=0;
    while(bfs()) {
        for(auto it=A[n].begin(); it!=A[n].end(); it++) {
            if(!viz[*it]||cap[*it][n]==flux[*it][n]) {
                continue;
            }
            int nod=n;
            dad[n]=*it;
            int ans=cap[dad[nod]][nod]-flux[dad[nod]][nod];
            while(nod) {
                ans=min(cap[dad[nod]][nod]-flux[dad[nod]][nod],ans);
                nod=dad[nod];
            }

            if(!ans) {
                continue;
            }

            fluxmax+=ans;
            nod=n;
            while(nod) {
                flux[dad[nod]][nod]+=ans;
                flux[nod][dad[nod]]-=ans;
                nod=dad[nod];
            }
        }
    }
    return fluxmax;
}

void afisare(int n) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(flux[i][j+n]==1) {
                cout<<i<<' '<<j<<'\n';
            }
        }
    }
}

int main() {
    int N;
    cin>>N;
    for(int i=1;i<=N;i++) {
        cin>>go[i]>>gi[i];
    }
    graf(N);
    cout<<maxflow()<<'\n';
    afisare(N);
    return 0;
}