Submission #2211784

---

Source Code Expand

#include <iostream> 
#include <sstream> 
#include <fstream> 
#include <string> 
#include <vector> 
#include <deque> 
#include <queue> 
#include <stack> 
#include <set> 
#include <map> 
#include <algorithm> 
#include <functional> 
#include <utility> 
#include <bitset> 
#include <cmath> 
#include <cstdlib> 
#include <ctime> 
#include <cstdio> 
 
using namespace std; 
 
#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++) 
#define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) 
 
#define COST_INF (1LL<<60)
#define CAP_INF (1LL<<60)
 
template <typename T> class MinCostFlow{ 
  private: 
   
  struct edge{int to; T cap; T cost; int rev;}; 
   
  int V; 
  vector <vector <edge> > adj; 
  vector <T> pot; 
   
  pair <T, T> dijkstra(int s, int t, T FLOW_BOUND){ 
    int i; 
     
    vector <int> used(V, 0); 
    vector <T> dist(V, COST_INF); 
    vector <pair <int, int> > path(V, make_pair(-1, -1)); 
     
    priority_queue <pair <T, int> > q; 
    dist[s] = 0; 
    q.push(make_pair(0, s)); 
     
    while(!q.empty()){ 
      int x = q.top().second; 
      q.pop(); 
      if(used[x]) continue; 
      used[x] = true; 
       
      REP(i,adj[x].size()){ 
        edge e = adj[x][i]; 
        int y = e.to; 
        if(e.cap > 0){ 
          T d = dist[x] + e.cost + pot[x] - pot[y]; 
          if(d < dist[y] && !used[y]){ 
            dist[y] = d; 
            path[y] = make_pair(x, i); 
            q.push(make_pair(-d, y)); 
          } 
        } 
      } 
    } 
     
    REP(i,V) pot[i] += dist[i]; 
     
    if(dist[t] == COST_INF) return make_pair(0, 0); 
     
    T f = FLOW_BOUND; 
    T sum = 0; 
     
    int x = t; 
    while(x != s){ 
      int y = path[x].first; 
      int id = path[x].second; 
      sum += adj[y][id].cost; 
      f = min(f, adj[y][id].cap); 
      x = y; 
    } 
     
    x = t; 
    while(x != s){ 
      int y = path[x].first; 
      int id = path[x].second; 
      adj[y][id].cap -= f; 
      int id2 = adj[y][id].rev; 
      adj[x][id2].cap += f; 
      x = y; 
    } 
     
    return make_pair(f, f * sum); 
  } 
   
  public: 
   
  MinCostFlow(int n){ 
    V = n; 
    adj.resize(V, vector <edge>(0)); 
    pot.resize(V, 0); 
  } 
   
  void add_edge(int s, int t, T f, T c){ 
    edge e1 = {t, f, c, adj[t].size()}; 
    edge e2 = {s, 0, -c, adj[s].size()}; 
    adj[s].push_back(e1); 
    adj[t].push_back(e2); 
  } 
   
  pair <T, T> mincostflow(int s, int t, T FLOW_BOUND = (1LL<<59)){ 
    pair <T, T> ans = make_pair(0LL, 0LL); 
     
    while(FLOW_BOUND > 0){ 
      pair <T, T> tmp = dijkstra(s, t, FLOW_BOUND); 
      if(tmp.first == 0) break; 
      ans.first += tmp.first; 
      ans.second += tmp.second; 
      FLOW_BOUND -= tmp.first; 
    } 
     
    return ans; 
  } 
   
}; 
 
int main(){
	int nn;
	scanf("%d",&nn);
	MinCostFlow<long long int> mcf(nn+2);
 
	for(int i=0; i<nn; i++){
		long long int x;
		scanf("%lld",&x);
		mcf.add_edge(nn, i, x, 0);
	}
	for(int i=0; i<nn; i++){
		long long int x;
		scanf("%lld",&x);
		mcf.add_edge(i, nn+1, x, 0);
	}
	for(int i=1; i<nn; i++){
		mcf.add_edge(i-1, i, CAP_INF, 1);
		mcf.add_edge(i, i-1, CAP_INF, 1);
	}
	printf("%lld\n",mcf.mincostflow(nn, nn+1).second);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In instantiation of ‘void MinCostFlow<T>::add_edge(int, int, T, T) [with T = long long int]’:
./Main.cpp:136:27:   required from here
./Main.cpp:106:38: warning: narrowing conversion of ‘(&((MinCostFlow<long long int>*)this)->MinCostFlow<long long int>::adj.std::vector<_Tp, _Alloc>::operator[]<std::vector<MinCostFlow<long long int>::edge, std::allocator<MinCostFlow<long long int>::edge> >, std::allocator<std::vector<MinCostFlow<long long int>::edge, std::allocator<MinCostFlow<long long int>::edge> > > >(((std::vector<std::vector<MinCostFlow<long long int>::edge, std::allocator<MinCostFlow<long long int>::edge> >, std::allocator<std::vector<MinCostFlow<long long int>::edge, std::allocator<MinCostFlow<long long int>::edge> > > >::size_type)t)))->std::vector<_Tp, _Alloc>::size<MinCostFlow<long long int>::edge, std::allocator<MinCostFlow<long long int>::edge> >()’ from ‘std::vector<MinCostFlow<long long int>::edge, std::allocator<MinCostFlow<long long int>::edge> >::size_type {aka long unsigned int}’ ...

Judge Result