Cod sursa(job #1389824)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 16 martie 2015 18:01:42
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#include <bitset>
#include <vector>
#define nmax 105
using namespace std;
ifstream fin("harta.in");
ofstream g("harta.out");
vector <int> v[2*nmax];
bitset <2*nmax> uz;
int f[2*nmax][2*nmax],c[2*nmax][2*nmax];
int t[2*nmax],sol;
int n,m,p,u,q[nmax*2];

int bfs()
{
    int i,x,y;
    uz.reset();
    p=1;u=1;
    q[1]=0;
    uz[0]=1;
    while (p<=u) {
        x=q[p];
        for (i=0;i<v[x].size();i++) {
            y=v[x][i];
            if (uz[y]==1||f[x][y]==c[x][y])
                continue;
            uz[y]=1;
            t[y]=x;
            q[++u]=y;
            if (y==m)
                return 1;
        }
        p++;
    }
    return 0;
}
int main()
{
    int i,j,x,y,minflow;
    fin>>n;m=2*n+1;
    for (i=1;i<=n;i++) {
        fin>>x>>y;
        v[0].push_back(i);
        v[i].push_back(0);
        c[0][i]=x;
        for (j=n+1;j<=2*n;j++)
            if (j!=n+i) {
                v[i].push_back(j);
                v[j].push_back(i);
                c[i][j]=1;
            }
        v[n+i].push_back(m);
        v[m].push_back(n+i);
        c[n+i][m]=y;
    }
    t[0]=-1;
    while (bfs()) {
        int minflow=1<<30;
        x=m;
        while (t[x]>=0) {
            minflow=min(minflow,c[t[x]][x]-f[t[x]][x]);
            x=t[x];
        }
        x=m;
        while (t[x]>=0) {
            f[t[x]][x]+=minflow;
            f[x][t[x]]-=minflow;
            x=t[x];
        }
    }
    for (i=1;i<=n;i++)
        for (j=n+1;j<=2*n;j++)
            if (i!=j&&f[i][j]==1)
                sol++;
    g<<sol<<'\n';
    for (i=1;i<=n;i++)
        for (j=n+1;j<=2*n;j++)
            if (i!=j&&f[i][j]==1)
                g<<i<<' '<<j-n<<'\n';
    return 0;
}