Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- 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)&¬Visited(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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement