Cod sursa(job #475130)

Utilizator mlazariLazari Mihai mlazari Data 6 august 2010 10:00:22
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<fstream>
#include<queue>

using namespace std;

#define NMAX 203

ifstream fi("harta.in");
ofstream fo("harta.out");

int n,m,i,j,s,d,fmin;
int c[NMAX][NMAX],f[NMAX][NMAX],t[NMAX];
bool viz[NMAX],vec[NMAX][NMAX];
queue<int> q;

bool bfs() {
  int nod,i;
  q.push(s);
  viz[s]=true;
  for(i=1;i<=d;++i) viz[i]=false;
  while(!q.empty()) {
    nod=q.front();
    q.pop();
    if(nod==d) continue;
    for(i=s;i<=d;++i)
     if(!viz[i] && vec[nod][i] && f[nod][i]<c[nod][i]) {
       t[i]=nod;
       q.push(i);
       viz[i]=true;
     }
  }
  return viz[d];
}

int main() {
  fi>>n;
  d=n+n+1;
  for(i=1;i<=n;++i) {
    fi>>c[s][i]>>c[n+i][d];
    m+=c[n+i][d];
  }
  for(i=1;i<=n;++i)
   for(j=n+1;j<=n+n;++j)
    if(i!=j) c[i][j]=1;
  for(i=1;i<=n;++i) {
    vec[s][i]=true;
    vec[i][s]=true;
    vec[n+i][d]=true;
    vec[d][n+i]=true;
  }
  for(i=1;i<=n;++i)
   for(j=n+1;j<=n+n;++j)
    if(j-i!=n) {
      vec[i][j]=true;
      vec[j][i]=true;
    }
  while(bfs()) {
    for(i=n+1;i<=n+n;++i)
     if(viz[i] && f[i][d]<c[i][d]) {
       t[d]=i;
       fmin=c[i][d]-f[i][d];
       for(j=d;j!=s;j=t[j])
        fmin=min(fmin,c[t[j]][j]-f[t[j]][j]);
       for(j=d;j!=s;j=t[j]) {
         f[t[j]][j]+=fmin;
         f[j][t[j]]-=fmin;
       }
     }
  }
  fo<<m<<"\n";
  for(i=1;i<=n;++i)
   for(j=n+1;j<=n+n;++j)
    if(f[i][j]) fo<<i<<" "<<j-n<<"\n";
  return 0;
}