Cod sursa(job #986501)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 18 august 2013 22:59:27
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");

#define LE 666

int st[LE],k,father[LE];
bool viz[LE*6];
int cap[LE][LE];

bool bfs(int s,int d) {
    st[(k=1)]=s;
    for(int i=0; i<=d; ++i) viz[i]=false;
    viz[s]=true;

    for(int i=1; i<=k; ++i)
        for(int j=0; j<=d; ++j)
            if (cap[st[i]][j]>0&&viz[j]==false) {
                viz[j]=true;
                st[++k]=j;
                father[j]=st[i];
                if (j==d) return true;
            }
    return false;
}

void mflow(int S,int D) {
    while (bfs(S,D)) {
        int nod=D;

        while (nod) {
       //  cout<<father[nod]<<" "<<nod<<"-----";
            cap[father[nod]][nod]--;
            cap[nod][father[nod]]++;
            nod=father[nod];

        }
     //   cout<<'\n';
    int i;
    //cout<<'\n';
      //  for(i=1;i<=4;++i) cout<<cap[0][i]<<" ";
    }
}

int n,i;

int main() {
    f>>n;
    for(i=1; i<=n; ++i) {
        int xx,yy;
        f>>xx>>yy;
        cap[0][i]=xx;
        cap[i+n][n+n+1]=yy;
    }

    for(i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j) if (i!=j)
                cap[i][j+n]=1;
    mflow(0,n+n+1);


    int M=0;
    for(i=1;i<=n;++i)
      for(int j=1;j<=n;++j) if (i!=j&&cap[i][j+n]==0) ++M;

    g<<M<<" "<<'\n';

    for(i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
           if (i!=j&&cap[i][j+n]==0) g<<i<<" "<<j<<'\n';

    // cout<<flow<<'\n';
    //g<<flow<<'\n'

    f.close();
    g.close();
    return 0;
}