Cod sursa(job #2295468)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 3 decembrie 2018 18:01:08
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <cstdio>
#include <vector>
#define DIM 210
#define INF 2000000000
using namespace std;
int s,d;
int f[DIM],dq[DIM],a[DIM][DIM],fl[DIM][DIM],ok,tt[DIM],vf[DIM];
vector <int> v[DIM];
int bfs (int s){
    int i,p,u,nod,vecin;
    for (i=s;i<=d;i++)
        f[i]=0;
    ok=0;
    p=u=1;
    dq[p]=s;
    f[s]=1;
    while (p<=u){
        nod=dq[p];
        for (i=0;i<v[nod].size();i++){
            vecin=v[nod][i];
            if (f[vecin]==0 && fl[nod][vecin]<a[nod][vecin]){
                f[vecin]=1;
                dq[++u]=vecin;
                tt[vecin]=nod;
            }
            if (vecin==d && fl[nod][vecin]<a[nod][vecin])
                vf[++ok]=nod;
        }
        p++;
    }
    return f[d];
}
int main()
{
    FILE *fin=fopen ("harta.in","r");
    FILE *fout=fopen ("harta.out","w");
    int n,i,x,y,j,nod,vecin,mini,flux;
    fscanf (fin,"%d",&n);
    s=0;
    d=2*n+1;
    for (i=1;i<=n;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[s].push_back(i);
        v[i].push_back(s);
        a[s][i]=x;
        v[i+n].push_back(d);
        v[d].push_back(i+n);
        a[i+n][d]=y;
    }
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++){
            if (i!=j){
                v[i].push_back(j+n);
                v[j+n].push_back(i);
                a[i][j+n]=1;
            }
        }
    tt[s]=-1;
    while (bfs(s)){
        for (i=1;i<=ok;i++){
            nod=vf[i]; // nod sunt vecinii destinatiei in care am ajuns
            vecin=d;
            mini=INF;
            while (nod!=-1){
                //printf ("%d ",nod);
                mini=min(mini,a[nod][vecin]-fl[nod][vecin]);
                vecin=nod;
                nod=tt[nod];
            }
            //printf ("\n");
            nod=vf[i];
            vecin=d;
            while (nod!=-1){
                fl[nod][vecin]+=mini;
                fl[vecin][nod]-=mini;
                vecin=nod;
                nod=tt[nod];
            }

        }
    }
    flux=0;
    for (i=1;i<=n;i++)
        flux+=fl[s][i];
    fprintf (fout,"%d\n",flux);
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (i!=j && fl[i][j+n])
                fprintf (fout,"%d %d\n",i,j);
    return 0;
}