Cod sursa(job #1207058)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 11 iulie 2014 23:02:20
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <vector>
#include<cstring>

using namespace std;

ifstream fin ("harta.in");
ofstream fout ("harta.out");

int v[310],q[310],t[310],c[310][310],f[310][310];
int n,i,x,y,u,p,sol,minim,j,m;

vector <int> l[310];

int bfs() {

    memset(v,0,sizeof(v));
    v[0]=1;
    t[0]=-1;
    p=u=1;
    q[1]=0;
    while (p<=u) {
        x=q[p];
        for (int i=0;i<l[x].size();i++) {
            y=l[x][i];
            if (v[y]==0 && c[x][y]>f[x][y]) {
                q[++u]=y;
                t[y]=x;
                v[y]=1;
            }
        }
        p++;
    }
    return v[n];
}

int main () {

    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>x>>y;
        l[0].push_back(i);
        l[i].push_back(0);
        c[0][i]=x;
        for (j=n+1;j<=2*n;j++) {
            if (j!=n+i) {
                l[i].push_back(j);
                l[j].push_back(i);
                c[i][j]=1;
            }
        }
        l[n+i].push_back(2*n+1);
        l[2*n+1].push_back(n+i);
        c[n+i][2*n+1]=y;
    }
    m=n;
    n*=2;
    n++;

    while (bfs()) {

        for (i=0;i<l[n].size();i++) {
            x=l[n][i];
            if (v[x]==1 && c[x][n]>f[x][n]){
                minim=c[x][n]-f[x][n];
                while (t[x]!=-1){
                    if (minim>c[t[x]][x]-f[t[x]][x])
                        minim=c[t[x]][x]-f[t[x]][x];
                    x=t[x];
                }
                x=l[n][i];
                f[x][n]+=minim;
                f[n][x]-=minim;
                while (t[x]!=-1){
                    f[t[x]][x]+=minim;
                    f[x][t[x]]-=minim;
                    x=t[x];
                }
                sol+=minim;
            }
        }
    }


    fout<<sol<<"\n";

    for (i=1;i<=m;i++)
        for (j=m+1;j<=2*m;j++)
            if (f[i][j]==1)
                fout<<i<<" "<<j-m<<"\n";

    return 0;
}