Tuenti Contest 16 (Pablo Moreno)

/*
    Author: Pablo Moreno Olalla
    Email address: darthbrevu@yahoo.es
*/
#include <list>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

inline void tokenize(const string &in,list<string> &out,char chr=' ')   {
    int pos1=0,pos2;
    for (;;)    {
        pos1=in.find_first_not_of(chr,pos1);
        if (pos1==string::npos) return;
        pos2=in.find_first_of(chr,pos1);
        if (pos2==string::npos) {
            out.push_back(in.substr(pos1));
            return;
        }   else out.push_back(in.substr(pos1,pos2-pos1));
        pos1=pos2;
    }
}

//I use a template because I need to read strings, but size_t is way faster to compare.
template<typename T> class DGraph   {
public:
    class Entry {
    public:
        T o;
        T d;
        int f;
        inline Entry()  {}
        inline Entry(T oo,T dd,int ff):o(oo),d(dd),f(ff)    {}
        inline bool operator==(const Entry &e) const    {
            return (o==e.o)&&(d==e.d);//&&(f==e.f);
        }
    };
    unsigned int size;
    T o;
    T d;
    list<Entry> sparseData;
};

template<typename T> int searchInVector(const T &e,const vector<T> &v)  {
    for (size_t i=0;i<v.size();++i) if (v[i]==e) return i;
    return -1;
}

template<typename T> bool translate(const DGraph<T> &in,DGraph<size_t> &out)    {
    out.size=in.size;
    vector<T> dic(0);
    dic.reserve(in.size);
    dic.push_back(in.o);
    dic.push_back(in.d);
    out.o=0;
    out.d=1;
    size_t idx=2;
    int io,id;
    for (typename list<typename DGraph<T>::Entry>::const_iterator it=in.sparseData.begin();it!=in.sparseData.end();++it)    {
        io=searchInVector(it->o,dic);
        if (io<0)   {
            io=dic.size();
            if (io>=out.size) return false;
            dic.push_back(it->o);
        }
        id=searchInVector(it->d,dic);
        if (id<0)   {
            id=dic.size();
            if (id>=out.size) return false;
            dic.push_back(it->d);
        }
        out.sparseData.push_back(DGraph<size_t>::Entry(io,id,it->f));
    }
    return true;
}

inline unsigned int getFlow(const list<DGraph<size_t>::Entry> &l)   {
    list<DGraph<size_t>::Entry>::const_iterator it=l.begin();
    unsigned int mv=it->f;
    for (++it;it!=l.end();++it) if (mv>it->f) mv=it->f;
    return mv;
}

bool notVisited(const list<DGraph<size_t>::Entry> &in,size_t pos)   {
    list<DGraph<size_t>::Entry>::const_iterator it=in.begin();
    if (it==in.end()) return true;
    else if (it->o==pos) return false;
    for (;it!=in.end();++it) if (it->d==pos) return false;
    return true;
}

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)   {
    size_t curr=o;
    DGraph<size_t>::Entry e;
    while (curr!=d) {
        bool assigned=false;
        for (size_t i=0;i<cap.size();++i) if ((cap[curr][i]>0)&&notVisited(out,i))  {
            e.f=static_cast<int>(cap[curr][i])-flow[curr][i];
            if (e.f>0)  {
                e.d=i;
                e.o=curr;
                out.push_back(e);
                curr=i;
                assigned=true;
                break;
            }
        }
        if (!assigned) return false;
    }
    return true;
}

class PathData  {
public:
    list<DGraph<size_t>::Entry> prevPath;
    DGraph<size_t>::Entry me;
};

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) {
    size_t curr=o;
    PathData pd;
    queue<PathData> nodeQ;
    //Generation of the first nodes.
    for (size_t i=0;i<cap.size();++i) if (cap[curr][i]>0)   {
        pd.me.f=static_cast<int>(cap[curr][i])-flow[curr][i];
        if (pd.me.f>0)  {
            pd.me.o=curr;
            pd.me.d=i;
            if (i==d)   {
                out.push_back(pd.me);
                return true;
            }   else nodeQ.push(pd);
        }
    }
    //Breadth-first search.
    while (!nodeQ.empty())  {
        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!)
        pd=nodeQ.front();
        nodeQ.pop();
        pd.prevPath.push_back(pd.me);
        curr=pd.me.d;
        for (size_t i=0;i<cap.size();++i) if (cap[curr][i]>0)   {
            pd.me.f=static_cast<int>(cap[curr][i])-flow[curr][i];
            if (pd.me.f>0)  {
                pd.me.o=curr;
                pd.me.d=i;
                if (i==d)   {
                    out=pd.prevPath;
                    out.push_back(pd.me);
                    return true;
                }   else if (find(pd.prevPath.begin(),pd.prevPath.end(),pd.me)==pd.prevPath.end()) nodeQ.push(pd);
            }
        }
    }
    return false;
}

unsigned int solve(DGraph<size_t> &in)  {
    size_t N=in.size;
    vector<vector<unsigned int> > cap(N,vector<unsigned int>(N,0));
    for (list<DGraph<size_t>::Entry>::const_iterator it=in.sparseData.begin();it!=in.sparseData.end();++it) cap[it->o][it->d]+=it->f;
    vector<vector<int> > flow(N,vector<int>(N,0));
    list<DGraph<size_t>::Entry> path;
    while (bfSearch(cap,flow,in.o,in.d,path))   {
        unsigned int f=getFlow(path);
        for (list<DGraph<size_t>::Entry>::const_iterator it=path.begin();it!=path.end();++it)   {
            flow[it->o][it->d]+=f;
            flow[it->d][it->o]-=f;
        }
        path.clear();
    }
    return accumulate(flow[in.o].begin(),flow[in.o].end(),0);
}

int main(int argc,char **argv)  {
    //The first two lines are not strictly necessary, but make the code a little more handy.
    if (argc>=2) freopen(argv[1],"r",stdin);
    if (argc>=3) freopen(argv[2],"w",stdout);
    string tmp;
    int res;
    list<string> toks;
    list<string> subtoks;
    while (!cin.eof())  {
        toks.clear();
        getline(cin,tmp);
        DGraph<string> prob;
        DGraph<string>::Entry ge;
        tokenize(tmp,toks);
        if (toks.size()<3) break;
        list<string>::const_iterator it=toks.begin();
        if (sscanf(it->c_str(),"%u",&prob.size)!=1) continue;
        ++it;
        prob.o=*it;
        ++it;
        prob.d=*it;
        ++it;
        ge.f=0;
        for (;it!=toks.end();++it)  {
            subtoks.clear();
            tokenize(*it,subtoks,',');
            if (subtoks.size()!=3) break;
            list<string>::const_iterator it2=subtoks.begin();
            ge.o=*it2;
            ++it2;
            ge.d=*it2;
            ++it2;
            if (sscanf(it2->c_str(),"%d",&ge.f)!=1) break;
            else prob.sparseData.push_back(ge);
        }
        if (ge.o==ge.d) continue;   //No actual problem. Max flow=infinite.
        DGraph<size_t> ep;
        if (!translate(prob,ep)) continue;
        cout<<solve(ep)<<endl;
    }
    return 0;
}