fork download 
  1. /// mincost by muoii
  2.  
  3. /// vn.spoj.com/problems/MINCOST/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define tag "spoj"
  8. #define maxn 0
  9. #define maxc 0
  10. #define oo 1000000007
  11. #define mid ((l+r)>>1)
  12. #define meset(a,x) memset(a,x,sizeof(a))
  13. #define loop(x) for(int LoOpEr=x;LoOpEr-->0;)
  14. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  15. struct network{
  16.  
  17.     int n;
  18.     ///data: E,adj,lev,cur
  19.     vector< vector<int> > adj;
  20.     vector<int> lev,inq,bef;
  21.     struct edge{
  22.         int depa,dest;
  23.         int cap,cost,flow;
  24.  
  25.         #define residual(e) ((e.flow<0?0:e.cap)-e.flow)
  26.         #define cost(e) ((e.flow<0?-1:1)*e.cost)
  27.     };
  28.     vector<edge> E;
  29.  
  30.     network(): n(0), E(0), adj(0), lev(0), inq(0), bef(0) {};
  31.  
  32.     network(const int &N): n(N), E(0), adj(N+1), lev(N+1), inq(N+1), bef(N+1) {};
  33.  
  34.     void add_edge(const int &u,const int &v,const int &cap,const int &cost,const bool &arcs)
  35.     {
  36.         adj[u].push_back(E.size());E.push_back({u,v,cap,cost,0});
  37.         adj[v].push_back(E.size());E.push_back({v,u,arcs?0:cap,cost,0});
  38.     }
  39.  
  40.     queue<int> Q;
  41.     bool augment(const int &s,const int &t)
  42.     {
  43.         for(int i=1;i<=n;i++) lev[i]=oo, inq[i]=0, bef[i]=0;
  44.  
  45.         lev[s]=0;Q.push(s);inq[s]=1;
  46.  
  47.         int u,v;
  48.         edge e;
  49.         while(Q.size())
  50.         {
  51.             u=Q.front(),Q.pop(),inq[u]=false;
  52.  
  53.             for(const int &ide: adj[u])
  54.             {
  55.                 e=E[ide];v=e.dest;
  56.  
  57.                 if(residual(e)>0 && lev[u]+cost(e)<lev[v])
  58.                 {
  59.                     lev[v]=lev[u]+cost(e);
  60.                     bef[v]=ide;
  61.                     if(!inq[v]) Q.push(v),inq[v]=1;
  62.                 }
  63.             }
  64.         }
  65.         return lev[t]<oo;
  66.     }
  67.  
  68.  
  69.     int augmenting(const int &s,const int &t)
  70.     {
  71.         int delta=oo;
  72.         for(int v=t;v!=s;v=E[bef[v]].depa) delta=min(delta,residual(E[bef[v]]));
  73.         for(int v=t;v!=s;v=E[bef[v]].depa) E[bef[v]].flow+=delta,E[bef[v]^1].flow-=delta;
  74.  
  75.         return delta;
  76.     }
  77.  
  78.     int MinCost;
  79.     int MaxFlow(const int &s,const int &t)
  80.     {
  81.         int rep=0,delta;
  82.  
  83.         MinCost=0;
  84.  
  85.         while(augment(s,t))
  86.         {
  87.             delta=augmenting(s,t);
  88.             rep+=delta;
  89.             MinCost+=delta*lev[t];
  90.         }
  91.         return rep;
  92.     }
  93. };
  94. int main()
  95. {
  96.     #ifdef dmdd
  97.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  98.     #endif // dmdd
  99.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  100.  
  101.     int n,m,k,s,t;
  102.     cin>>n>>m>>k>>s>>t;
  103.  
  104.     network net(n+1);
  105.     net.add_edge(n+1,s,k,0,1);
  106.     s=n+1;
  107.  
  108.     int a,b,c,d;
  109.     vector< vector<int> > C,D;
  110.     C=D=vector< vector<int> >(n+1,vector<int>(n+1,-1));
  111.  
  112.     loop(m)
  113.     {
  114.         cin>>a>>b>>c>>d;
  115.         C[a][b]=C[b][a]=c;
  116.         D[a][b]=D[b][a]=d;
  117.     }
  118.  
  119.     for(int u=1;u<=n;u++)
  120.         for(int v=u+1;v<=n;v++)
  121.             if(D[u][v]>=0)
  122.                 net.add_edge(u,v,D[u][v],C[u][v],0);
  123.  
  124.     if(net.MaxFlow(s,t)==k)
  125.     {
  126.         cout<<net.MinCost<<"\n";
  127.  
  128.         for(const auto &e: net.E)
  129.             if(e.depa<s && e.flow>0)
  130.                 cout<<e.depa<<" "<<e.dest<<" "<<e.flow<<"\n";
  131.  
  132.         cout<<"0 0 0";
  133.     }
  134.     else cout<<-1;
  135.  
  136.     return 0;
  137. }
  138.  
  139.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin 
6 8 5 1 6
1 2 1 2
1 4 3 4
2 3 1 4
2 5 5 2
3 4 2 4
3 6 1 2
4 6 4 1
5 6 6 2
stdout 
43
1 2 2
1 4 3
2 5 2
4 3 2
3 6 2
4 6 1
5 6 2
0 0 0
https://ideone.com/4aZ7Ir
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!