Cod sursa(job #1204751)

Utilizator apopeid15Apopei Daniel apopeid15 Data 3 iulie 2014 19:46:13
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

const int INF = 1000000000;

int n,i,k,nod,p,u,x,y,j,Min;

int q[200],C[200][200],F[200][200],T[200],sol[20000][2];

bool viz[1000];

vector<int> L[200];
vector<int>::iterator it;

inline int minim(int a, int b) {
    return a<b ? a : b;
}

bool BFS() {
    p=u=1;
    memset(viz,0,n+1);
    q[1]=0;
    viz[0]=1;
    while(p<=u) {
        if(q[p]==n) {
            p++;
            continue;
        }
        nod=q[p];
        for(it=L[nod].begin();it!=L[nod].end();it++) {
            if(viz[*it] || C[nod][*it]==F[nod][*it])
                continue;
            u++;
            q[u]=*it;
            viz[*it]=1;
            T[*it]=nod;
        }
        p++;
    }
    return viz[n];
}

int main() {
    ifstream f("harta.in");
    ofstream g("harta.out");
    f>>n;
    for(i=1;i<=n;i++) {
        f>>x>>y;
        C[0][i]=x;
        C[n+i][2*n+1]=y;
        L[0].push_back(i);
        L[i].push_back(0);
        L[n+i].push_back(2*n+1);
        L[2*n+1].push_back(n+i);
        for(j=1;j<=n;j++)
            if(i!=j) {
                C[i][n+j]=1;
                L[i].push_back(n+j);
                L[n+j].push_back(i);
            }
    }
    n<<=1;
    n++;
    while( BFS() ) {
        for(it=L[n].begin();it!=L[n].end();it++) {
            if(!viz[*it] || C[*it][n]==F[*it][n])
                continue;
            T[n]=*it;
            Min=INF;
            for(i=n;i!=0;i=T[i])
                Min=minim(Min,C[T[i]][i]-F[T[i]][i]);
            if(Min==0)
                continue;
            for(i=n;i!=0;i=T[i]) {
                F[T[i]][i]+=Min;
                F[i][T[i]]-=Min;
            }
        }
    }
    for(i=1;i<=n/2;i++) {
        for(it=L[i].begin();it!=L[i].end();it++)
            if(*it!=0 && F[i][*it]!=0) {
                k++;
                sol[k][0]=i;
                sol[k][1]=*it-n/2;
            }
    }
    g<<k<<"\n";
    for(i=1;i<=k;i++)
        g<<sol[i][0]<<" "<<sol[i][1]<<"\n";
    return 0;
}