1088-School Excursion

問題概要

日本語なので略

解法

グラフを構築し，最小費用流をする．
基本的に流量はINFだが，同じ時刻に到着する列車については流量1の辺を張るようにする．

実装(C++)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define REP(i,x)for(int i=0;i<x;i++)
struct E{int dst,cost,cap,rev;};
vector<E> G[100000];
int m[100],x[100][20],y[100][20],c[100][20],n,g,v;
void add_edge(int s,int d,int c,int f){
  G[s].push_back((E){d,c,f,G[d].size()});
  G[d].push_back((E){s,-c,0,G[s].size()-1});
}
void min_cost_flow(int s,int t,int f){
  typedef pair<int,int> P;
  int res=0,V=v,es=f;
  vector<int> prevv(V),preve(V);
  while(f>0){
    vector<int> dist(V,99999999);
    bool update=true;
    dist[s]=0;
    while(update){
      update=false;
      REP(v,V){
        if(dist[v]==99999999)continue;
        REP(i,G[v].size()){
          E &e=G[v][i];
          if(e.cap>0&&dist[e.dst]>dist[v]+e.cost){
            dist[e.dst]=dist[v]+e.cost;
            prevv[e.dst]=v;
            preve[e.dst]=i;
            update=true;
          }
        }
      }
    }
    if(dist[t]==99999999){
      cout<<es-f<<" "<<res<<endl;
      return;
    }
    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]){
      E &e=G[prevv[v]][preve[v]];
      e.cap-=d;
      G[v][e.rev].cap+=d;
    }
  }
  cout<<es-f<<" "<<res<<endl;
  return;
}
int main(){
  for(;cin>>n,n;v=0){
    fill(G,G+10000,vector<E>());
    REP(i,n-1){
      cin>>m[i];
      REP(j,m[i])cin>>x[i][j]>>y[i][j]>>c[i][j];
    }
    cin>>g;
    REP(j,n-1){
      REP(i,m[j]){
        bool ok=1;
        REP(k,i){
          if(y[j][i]==y[j][k])ok=0;
        }
        if(!ok)continue;
        REP(k,m[j]){
          if(y[j][i]==y[j][k]){
            add_edge(v+k,v+m[j]+i,c[j][k],1);
          }
        }
        add_edge(v+m[j]+i,v+m[j]*2+i,0,1);
      }
      v+=m[j]*3;
    }
    v=m[0]*3;
    for(int j=1;j<n-1;j++){
      REP(p,m[j-1])REP(q,m[j]){
        if(y[j-1][p]<=x[j][q])
          add_edge(v-m[j-1]+p,v+q,0,9999);
      }
      v+=m[j]*3;
    }
    REP(i,m[0]){
      add_edge(v,i,0,9999);
    }
    REP(i,m[n-2]){
      add_edge(v-m[n-2]+i,v+1,0,9999);
    }
    v+=2;
    min_cost_flow(v-2,v-1,g);
  }
}