SHARE
TWEET

Tuenti Contest 16 (Pablo Moreno)

Nbrevu Jun 20th, 2011 830 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.         Author: Pablo Moreno Olalla
  3.         Email address: darthbrevu@yahoo.es
  4. */
  5. #include <list>
  6. #include <queue>
  7. #include <cstdio>
  8. #include <string>
  9. #include <vector>
  10. #include <climits>
  11. #include <numeric>
  12. #include <sstream>
  13. #include <iostream>
  14. #include <algorithm>
  15.  
  16. using namespace std;
  17.  
  18. inline void tokenize(const string &in,list<string> &out,char chr=' ')   {
  19.         int pos1=0,pos2;
  20.         for (;;)        {
  21.                 pos1=in.find_first_not_of(chr,pos1);
  22.                 if (pos1==string::npos) return;
  23.                 pos2=in.find_first_of(chr,pos1);
  24.                 if (pos2==string::npos) {
  25.                         out.push_back(in.substr(pos1));
  26.                         return;
  27.                 }       else out.push_back(in.substr(pos1,pos2-pos1));
  28.                 pos1=pos2;
  29.         }
  30. }
  31.  
  32. //I use a template because I need to read strings, but size_t is way faster to compare.
  33. template<typename T> class DGraph       {
  34. public:
  35.         class Entry     {
  36.         public:
  37.                 T o;
  38.                 T d;
  39.                 int f;
  40.                 inline Entry()  {}
  41.                 inline Entry(T oo,T dd,int ff):o(oo),d(dd),f(ff)        {}
  42.                 inline bool operator==(const Entry &e) const    {
  43.                         return (o==e.o)&&(d==e.d);//&&(f==e.f);
  44.                 }
  45.         };
  46.         unsigned int size;
  47.         T o;
  48.         T d;
  49.         list<Entry> sparseData;
  50. };
  51.  
  52. template<typename T> int searchInVector(const T &e,const vector<T> &v)  {
  53.         for (size_t i=0;i<v.size();++i) if (v[i]==e) return i;
  54.         return -1;
  55. }
  56.  
  57. template<typename T> bool translate(const DGraph<T> &in,DGraph<size_t> &out)    {
  58.         out.size=in.size;
  59.         vector<T> dic(0);
  60.         dic.reserve(in.size);
  61.         dic.push_back(in.o);
  62.         dic.push_back(in.d);
  63.         out.o=0;
  64.         out.d=1;
  65.         size_t idx=2;
  66.         int io,id;
  67.         for (typename list<typename DGraph<T>::Entry>::const_iterator it=in.sparseData.begin();it!=in.sparseData.end();++it)    {
  68.                 io=searchInVector(it->o,dic);
  69.                 if (io<0)       {
  70.                         io=dic.size();
  71.                         if (io>=out.size) return false;
  72.                         dic.push_back(it->o);
  73.                 }
  74.                 id=searchInVector(it->d,dic);
  75.                 if (id<0)       {
  76.                         id=dic.size();
  77.                         if (id>=out.size) return false;
  78.                         dic.push_back(it->d);
  79.                 }
  80.                 out.sparseData.push_back(DGraph<size_t>::Entry(io,id,it->f));
  81.         }
  82.         return true;
  83. }
  84.  
  85. inline unsigned int getFlow(const list<DGraph<size_t>::Entry> &l)       {
  86.         list<DGraph<size_t>::Entry>::const_iterator it=l.begin();
  87.         unsigned int mv=it->f;
  88.         for (++it;it!=l.end();++it) if (mv>it->f) mv=it->f;
  89.         return mv;
  90. }
  91.  
  92. bool notVisited(const list<DGraph<size_t>::Entry> &in,size_t pos)       {
  93.         list<DGraph<size_t>::Entry>::const_iterator it=in.begin();
  94.         if (it==in.end()) return true;
  95.         else if (it->o==pos) return false;
  96.         for (;it!=in.end();++it) if (it->d==pos) return false;
  97.         return true;
  98. }
  99.  
  100. bool search(const vector<vector<unsigned int> > &cap,const vector<vector<int> > &flow,size_t o,size_t d,list<DGraph<size_t>::Entry> &out)       {
  101.         size_t curr=o;
  102.         DGraph<size_t>::Entry e;
  103.         while (curr!=d) {
  104.                 bool assigned=false;
  105.                 for (size_t i=0;i<cap.size();++i) if ((cap[curr][i]>0)&&notVisited(out,i))      {
  106.                         e.f=static_cast<int>(cap[curr][i])-flow[curr][i];
  107.                         if (e.f>0)      {
  108.                                 e.d=i;
  109.                                 e.o=curr;
  110.                                 out.push_back(e);
  111.                                 curr=i;
  112.                                 assigned=true;
  113.                                 break;
  114.                         }
  115.                 }
  116.                 if (!assigned) return false;
  117.         }
  118.         return true;
  119. }
  120.  
  121. class PathData  {
  122. public:
  123.         list<DGraph<size_t>::Entry> prevPath;
  124.         DGraph<size_t>::Entry me;
  125. };
  126.  
  127. bool bfSearch(const vector<vector<unsigned int> > &cap,const vector<vector<int> > &flow,size_t o,size_t d,list<DGraph<size_t>::Entry> &out)     {
  128.         size_t curr=o;
  129.         PathData pd;
  130.         queue<PathData> nodeQ;
  131.         //Generation of the first nodes.
  132.         for (size_t i=0;i<cap.size();++i) if (cap[curr][i]>0)   {
  133.                 pd.me.f=static_cast<int>(cap[curr][i])-flow[curr][i];
  134.                 if (pd.me.f>0)  {
  135.                         pd.me.o=curr;
  136.                         pd.me.d=i;
  137.                         if (i==d)       {
  138.                                 out.push_back(pd.me);
  139.                                 return true;
  140.                         }       else nodeQ.push(pd);
  141.                 }
  142.         }
  143.         //Breadth-first search.
  144.         while (!nodeQ.empty())  {
  145.                 if (nodeQ.size()>100000) return search(cap,flow,o,d,out);       //This is a very stupid trick that WORKS. Otherwise, bfsearch can take forever (but, when it doesn't, it yields a better solution!)
  146.                 pd=nodeQ.front();
  147.                 nodeQ.pop();
  148.                 pd.prevPath.push_back(pd.me);
  149.                 curr=pd.me.d;
  150.                 for (size_t i=0;i<cap.size();++i) if (cap[curr][i]>0)   {
  151.                         pd.me.f=static_cast<int>(cap[curr][i])-flow[curr][i];
  152.                         if (pd.me.f>0)  {
  153.                                 pd.me.o=curr;
  154.                                 pd.me.d=i;
  155.                                 if (i==d)       {
  156.                                         out=pd.prevPath;
  157.                                         out.push_back(pd.me);
  158.                                         return true;
  159.                                 }       else if (find(pd.prevPath.begin(),pd.prevPath.end(),pd.me)==pd.prevPath.end()) nodeQ.push(pd);
  160.                         }
  161.                 }
  162.         }
  163.         return false;
  164. }
  165.  
  166. unsigned int solve(DGraph<size_t> &in)  {
  167.         size_t N=in.size;
  168.         vector<vector<unsigned int> > cap(N,vector<unsigned int>(N,0));
  169.         for (list<DGraph<size_t>::Entry>::const_iterator it=in.sparseData.begin();it!=in.sparseData.end();++it) cap[it->o][it->d]+=it->f;
  170.         vector<vector<int> > flow(N,vector<int>(N,0));
  171.         list<DGraph<size_t>::Entry> path;
  172.         while (bfSearch(cap,flow,in.o,in.d,path))       {
  173.                 unsigned int f=getFlow(path);
  174.                 for (list<DGraph<size_t>::Entry>::const_iterator it=path.begin();it!=path.end();++it)   {
  175.                         flow[it->o][it->d]+=f;
  176.                         flow[it->d][it->o]-=f;
  177.                 }
  178.                 path.clear();
  179.         }
  180.         return accumulate(flow[in.o].begin(),flow[in.o].end(),0);
  181. }
  182.  
  183. int main(int argc,char **argv)  {
  184.         //The first two lines are not strictly necessary, but make the code a little more handy.
  185.         if (argc>=2) freopen(argv[1],"r",stdin);
  186.         if (argc>=3) freopen(argv[2],"w",stdout);
  187.         string tmp;
  188.         int res;
  189.         list<string> toks;
  190.         list<string> subtoks;
  191.         while (!cin.eof())      {
  192.                 toks.clear();
  193.                 getline(cin,tmp);
  194.                 DGraph<string> prob;
  195.                 DGraph<string>::Entry ge;
  196.                 tokenize(tmp,toks);
  197.                 if (toks.size()<3) break;
  198.                 list<string>::const_iterator it=toks.begin();
  199.                 if (sscanf(it->c_str(),"%u",&prob.size)!=1) continue;
  200.                 ++it;
  201.                 prob.o=*it;
  202.                 ++it;
  203.                 prob.d=*it;
  204.                 ++it;
  205.                 ge.f=0;
  206.                 for (;it!=toks.end();++it)      {
  207.                         subtoks.clear();
  208.                         tokenize(*it,subtoks,',');
  209.                         if (subtoks.size()!=3) break;
  210.                         list<string>::const_iterator it2=subtoks.begin();
  211.                         ge.o=*it2;
  212.                         ++it2;
  213.                         ge.d=*it2;
  214.                         ++it2;
  215.                         if (sscanf(it2->c_str(),"%d",&ge.f)!=1) break;
  216.                         else prob.sparseData.push_back(ge);
  217.                 }
  218.                 if (ge.o==ge.d) continue;       //No actual problem. Max flow=infinite.
  219.                 DGraph<size_t> ep;
  220.                 if (!translate(prob,ep)) continue;
  221.                 cout<<solve(ep)<<endl;
  222.         }
  223.         return 0;
  224. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top