Cod sursa(job #1453729)

Utilizator DjokValeriu Motroi Djok Data 24 iunie 2015 15:02:04
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<bits/stdc++.h>
using namespace std;

typedef struct lnod {
    int info;
    lnod *next;
}*nod;

const int INF=0x3f3f3f3f;

int i,j,n,x,y,rs,a[205][205],t[205],q[205],st,dr;
bool viz[205];
nod lda[205];

void add(int x,nod &y) {
    nod p=new lnod;
    p->info=x;
    p->next=y;
    y=p;
}

void update() {
    int nod,flow=INF;

    for(nod=n+n+1;nod;nod=t[nod])
    flow=min(flow,a[t[nod]][nod]);

    rs+=flow;

    for(nod=n+n+1;nod!=0;nod=t[nod])
    a[t[nod]][nod]-=flow,a[nod][t[nod]]+=flow;
}

bool bfs() {
    bool u=0;
    memset(viz,0,sizeof(viz));
    q[1]=0; viz[0]=1; t[0]=0;
    for(st=dr=1;st<=dr;++st)
     for(nod p=lda[q[st]];p;p=p->next)
     if(a[q[st]][p->info] && !viz[p->info])
     {
       viz[p->info]=1; t[p->info]=q[st]; q[++dr]=p->info;
       if(p->info==n+n+1) update(),viz[n+n+1]=0,--dr,u=1;
     }

    return u;
}

int main()
{
  ifstream cin("harta.in");
  ofstream cout("harta.out");

  cin>>n;
  for(i=1;i<=n;++i)
  {
    cin>>x>>y;
    add(i,lda[0]); a[0][i]=x;
    add(0,lda[i]);
    add(n+i,lda[n+n+1]);
    add(n+n+1,lda[i+n]); a[n+i][n+n+1]=y;
  }

  for(i=1;i<=n;++i)
   for(j=n+1;j<=n+n;++j)
   if(i!=j-n) add(j,lda[i]),a[i][j]=1,add(i,lda[j]);

  while(bfs());

  cout<<rs<<'\n';
  for(i=1;i<=n;++i)
   for(j=n+1;j<=n+n;++j)
   if(a[j][i]) cout<<i<<' '<<j-n<<'\n';

 return 0;
}