This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub mugen1337/procon
#include "Flow/PrimalDual.hpp"
// https://ei1333.github.io/library/graph/flow/primal-dual.hpp template<typename flow_t, typename cost_t> struct PrimalDual{ struct edge{ int to; flow_t cap; cost_t cost; int rev;//この辺の逆辺がg[from]の何番目にあるか bool isrev; }; vector<vector<edge>> graph; vector<cost_t> potential,min_cost; vector<int> prevv,preve;//点,辺 const cost_t TINF; PrimalDual(int V):graph(V),TINF(numeric_limits<cost_t>::max()){} void add_edge(int from,int to,flow_t cap,cost_t cost){ graph[from].push_back((edge){to,cap,cost,(int)graph[to].size(),false}); graph[to].push_back((edge){from,0,-cost,(int)graph[from].size()-1,true}); } cost_t min_cost_flow(int s,int t,flow_t f,bool &ok){ int V=(int)graph.size(); cost_t ret=0; using Pi=pair<cost_t,int>; priority_queue<Pi,vector<Pi>,greater<Pi>> que; potential.assign(V,0); preve.assign(V,-1); prevv.assign(V,-1); while(f>0){ min_cost.assign(V,TINF); que.emplace(0,s); min_cost[s]=0; //dijkstraパート while(!que.empty()){ Pi p=que.top();que.pop(); if(min_cost[p.second]<p.first) continue; for(int i=0;i<(int)graph[p.second].size();i++){ edge &e=graph[p.second][i]; cost_t nextCost=min_cost[p.second]+e.cost+potential[p.second]-potential[e.to]; if(e.cap>0 and min_cost[e.to]>nextCost){ min_cost[e.to]=nextCost; prevv[e.to]=p.second,preve[e.to]=i; que.emplace(min_cost[e.to],e.to); } } } if(min_cost[t]==TINF){ ok=false; return ret; } // dijkstraの結果に応じてpotentialを調節 for(int v=0;v<V;v++)potential[v]+=min_cost[v]; flow_t addflow=f; for(int v=t;v!=s;v=prevv[v]){ addflow=min(addflow,graph[prevv[v]][preve[v]].cap); } f-=addflow; ret+=addflow*potential[t]; for(int v=t;v!=s;v=prevv[v]){ edge &e=graph[prevv[v]][preve[v]]; e.cap-=addflow; graph[v][e.rev].cap+=addflow; } } ok=true; return ret; } void output(){ for(int i=0;i<graph.size();i++){ for(auto &e:graph[i]){ if(e.isrev)continue; auto &rev_e=graph[e.to][e.rev]; cout<<i<<"->"<<e.to<<" (flow: "<<rev_e.cap<<" / "<<rev_e.cap+e.cap<<")"<<endl; } } } };
#line 1 "Flow/PrimalDual.hpp" // https://ei1333.github.io/library/graph/flow/primal-dual.hpp template<typename flow_t, typename cost_t> struct PrimalDual{ struct edge{ int to; flow_t cap; cost_t cost; int rev;//この辺の逆辺がg[from]の何番目にあるか bool isrev; }; vector<vector<edge>> graph; vector<cost_t> potential,min_cost; vector<int> prevv,preve;//点,辺 const cost_t TINF; PrimalDual(int V):graph(V),TINF(numeric_limits<cost_t>::max()){} void add_edge(int from,int to,flow_t cap,cost_t cost){ graph[from].push_back((edge){to,cap,cost,(int)graph[to].size(),false}); graph[to].push_back((edge){from,0,-cost,(int)graph[from].size()-1,true}); } cost_t min_cost_flow(int s,int t,flow_t f,bool &ok){ int V=(int)graph.size(); cost_t ret=0; using Pi=pair<cost_t,int>; priority_queue<Pi,vector<Pi>,greater<Pi>> que; potential.assign(V,0); preve.assign(V,-1); prevv.assign(V,-1); while(f>0){ min_cost.assign(V,TINF); que.emplace(0,s); min_cost[s]=0; //dijkstraパート while(!que.empty()){ Pi p=que.top();que.pop(); if(min_cost[p.second]<p.first) continue; for(int i=0;i<(int)graph[p.second].size();i++){ edge &e=graph[p.second][i]; cost_t nextCost=min_cost[p.second]+e.cost+potential[p.second]-potential[e.to]; if(e.cap>0 and min_cost[e.to]>nextCost){ min_cost[e.to]=nextCost; prevv[e.to]=p.second,preve[e.to]=i; que.emplace(min_cost[e.to],e.to); } } } if(min_cost[t]==TINF){ ok=false; return ret; } // dijkstraの結果に応じてpotentialを調節 for(int v=0;v<V;v++)potential[v]+=min_cost[v]; flow_t addflow=f; for(int v=t;v!=s;v=prevv[v]){ addflow=min(addflow,graph[prevv[v]][preve[v]].cap); } f-=addflow; ret+=addflow*potential[t]; for(int v=t;v!=s;v=prevv[v]){ edge &e=graph[prevv[v]][preve[v]]; e.cap-=addflow; graph[v][e.rev].cap+=addflow; } } ok=true; return ret; } void output(){ for(int i=0;i<graph.size();i++){ for(auto &e:graph[i]){ if(e.isrev)continue; auto &rev_e=graph[e.to][e.rev]; cout<<i<<"->"<<e.to<<" (flow: "<<rev_e.cap<<" / "<<rev_e.cap+e.cap<<")"<<endl; } } } };