Cod sursa(job #1250743)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 28 octombrie 2014 15:18:26
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define inf 2147000000
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
 vector <int> v[205];
 queue <int> q;
 int n,use[205],ant[205],fol[205][205],c[205][205],s,t,x1[100005],x2[100005],k;

 int BFS()
 {  int i,nod,nod2;
   memset(use,0,sizeof(use));
   memset(ant,0,sizeof(ant));
     q.push(s); use[s]=1;

     while(!q.empty())
     { nod=q.front(); q.pop();
        if (nod==t) continue;

        for(i=0;i<v[nod].size();i++)
        { nod2=v[nod][i];
            if (!use[nod2] && fol[nod][nod2]<c[nod][nod2])
            { q.push(nod2);
              use[nod2]=1;
              ant[nod2]=nod;
            }
        }
     }

  return use[t]>0;
 }
 void Flux()
 { int i,x,j,n1,n2,res;

     while(BFS())
     {
       for(i=0;i<v[t].size();i++)
       { x=v[t][i]; res=c[x][t]-fol[x][t];
           while(ant[x])
           { n1=ant[x]; n2=x;
              res=min(res,c[n1][n2]-fol[n1][n2]);
             x=ant[x];
           }

         x=v[t][i]; fol[x][t]+=res; fol[t][x]-=res;

          while(ant[x])
           { n1=ant[x]; n2=x;
              fol[n1][n2]+=res;
              fol[n2][n1]-=res;
             x=ant[x];
           }
       }
     }

    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
      if (fol[i][j+n]>0)
        {k++; x1[k]=i; x2[k]=j; }

     g<<k<<"\n";
    for(i=1;i<=k;i++)
     g<<x1[i]<<" "<<x2[i]<<"\n";
 }
int main()
{ int i,j,x,y;
    f>>n;
     s=2*n+1; t=2*n+2;

    for(i=1;i<=n;i++)
    {  f>>x>>y;
       v[s].push_back(i); v[i].push_back(s); c[s][i]+=x;
       v[i+n].push_back(t); v[t].push_back(i+n); c[i+n][t]+=y;
    }

    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
      if (i!=j)
       {v[i].push_back(j+n); v[j+n].push_back(i); c[i][j+n]+=1;}

       Flux();
   return 0;
}