Submission #3958753

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
int mod=1e9+7;
int mod2=998244353;
const int INF=1e9;

const int MAX_V=100;
struct edge{int to,cap,cost,rev;};

int V;
vector<edge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];

void add_edge(int from,int to,int cap,int cost){
  G[from].push_back((edge){to,cap,cost,G[to].size()});
  G[to].push_back((edge){from,0,-cost,G[from].size()-1});
}

int min_cost_flow(int s,int t,int f){
  int res=0;
  while(f>0){
    fill(dist,dist+V,INF);
    dist[s]=0;
    bool update=true;
    while(update){
      update=false;
      for(int v=0;v<V;v++){
        if(dist[v]==INF)continue;
        for(int i=0;i<G[v].size();i++){
          edge &e=G[v][i];
          if(e.cap>0&&dist[e.to]>dist[v]+e.cost){
            dist[e.to]=dist[v]+e.cost;
            prevv[e.to]=v;
            preve[e.to]=i;
            update=true;
          }
        }
      }
    }
    if(dist[t]==INF){
      return -1;
    }

    int d=f;
    for(int v=t;v!=s;v=prevv[v]){
      d=min(d,G[prevv[v]][preve[v]].cap);
    }
    f-=d;
    res+=d*dist[t];
    for(int v=t;v!=s;v=prevv[v]){
      edge &e=G[prevv[v]][preve[v]];
      e.cap-=d;
      G[v][e.rev].cap+=d;
    }
  }
  return res;
}

signed main(){
  int n,m;
  cin>>n>>m;
  vector<int> ax(n),ay(n);
  vector<int> bx(n),by(n);
  vector<int> mg(m);
  string s;
  for(int i=0;i<n;i++)cin>>s>>ax[i]>>ay[i];
  for(int i=0;i<m;i++)cin>>s>>mg[i]>>bx[i]>>by[i];
  V=n+m+2;
  for(int i=1;i<=n;i++)add_edge(0,i,1,0);
  for(int i=n+1;i<=n+m;i++)add_edge(i,n+m+1,1,0);
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      add_edge(i+1,n+j+1,1,-1*(abs(ax[i]-bx[j])+abs(ay[i]-by[j])));
    }
  }
  //s=0;
  //n=1~n;
  //n+1~n+m;
  //t=n+m+1
  cout<<-1*min_cost_flow(0,n+m+1,n)<<endl;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void add_edge(long long int, long long int, long long int, long long int)’:
./Main.cpp:18:50: warning: narrowing conversion of ‘G[to].std::vector<_Tp, _Alloc>::size<edge, std::allocator<edge> >()’ from ‘std::vector<edge>::size_type {aka long unsigned int}’ to ‘long long int’ inside { } [-Wnarrowing]
   G[from].push_back((edge){to,cap,cost,G[to].size()});
                                                  ^
./Main.cpp:19:53: warning: narrowing conversion of ‘(G[from].std::vector<_Tp, _Alloc>::size<edge, std::allocator<edge> >() + 18446744073709551615ul)’ from ‘std::vector<edge>::size_type {aka long unsigned int}’ to ‘long long int’ inside { } [-Wnarrowing]
   G[to].push_back((edge){from,0,-cost,G[from].size()-1});
                                                     ^

Judge Result