Cod sursa(job #1674825)

Utilizator DjokValeriu Motroi Djok Data 4 aprilie 2016 21:21:35
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 1.39 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;
}