Maximum-Cup 2013

Submission #3958753

Source codeソースコード

#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

Task問題 F - 3人の騎士と1匹の犬
User nameユーザ名 七宮
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 RE
Score得点 0
Source lengthソースコード長 1880 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

./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});
^

Test case

Set

Set name Score得点 / Max score Cases
All 0 / 100 00-sample,01-minimum,02-maximum,50-random-00,50-random-01,50-random-02,50-random-03,50-random-04,50-random-05,50-random-06,50-random-07,50-random-08,50-random-09,50-random-10,50-random-11,50-random-12,50-random-13,50-random-14,50-random-15,50-random-16,50-random-17,50-random-18,50-random-19

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00-sample WA
01-minimum WA
02-maximum RE
50-random-00 RE
50-random-01 WA
50-random-02 RE
50-random-03 RE
50-random-04 WA
50-random-05 RE
50-random-06 WA
50-random-07 WA
50-random-08 RE
50-random-09 RE
50-random-10 WA
50-random-11 RE
50-random-12 WA
50-random-13 WA
50-random-14 WA
50-random-15 RE
50-random-16 RE
50-random-17 WA
50-random-18 WA
50-random-19 RE