Nbrevu

Tuenti Contest 16 (Pablo Moreno)

Jun 20th, 2011
1,065
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