LiveArchive 6905 Two Yachts

問題

https://icpcarchive.ecs.baylor.edu/external/69/6905.pdf

2隻の船がある。また、(船の運用期間, 得られる金額) のペアで表された企画が個与えられる。
2隻の船だけを用いて運用できるようなスケジューリングをして、得られる金額の総和を最大化せよ。
同じ企画を2度以上採用することはできない。

解法

最小費用流を流す。
金額に対して負辺を張ることで、最大利益を求めることができる。
流量は船の隻数であり、それぞれの船について運用のスケジュールを立てる。
2つの船の運用を独立にスケジューリングすることはできないので、フローを流して解くと良い。

負辺があるが、負閉路はないのでDijkstraの方法でも動く。

#include <bits/stdc++.h>
 
using namespace std;
 
#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
 
typedef long long ll;
int const inf = 1<<29;
 
struct edge {
  int to, cap; ll cost; int rev;
  edge(int t, ll ca, ll co, int r) : to(t), cap(ca), cost(co), rev(r) {}
};
 
struct primal_dual {
 
  vector<vector<edge>> G;
  vector<ll> h;
  vector<ll> dist;
  vector<int> prevv, preve;
 
  primal_dual(int V) : G(V), h(V), dist(V), prevv(V), preve(V) {}
 
  void add_edge(int from, int to, ll cap, ll cost) {
    G[from].emplace_back(to, cap, cost, G[to].size());
    G[to].emplace_back(from, 0, -cost, G[from].size()-1);
  }
 
  int min_cost_flow(int s, int t, int f) {
    int ret = 0;
    fill(h.begin(), h.end(), 0);
    while(f > 0) {
      typedef pair<int, int> P;
      priority_queue<P, vector<P>, greater<P>> pq;
      fill(dist.begin(), dist.end(), inf);
      dist[s] = 0;
      pq.emplace(0, s);
      while(!pq.empty()) {
        P p = pq.top(); pq.pop();
        int v = p.second;
        if(dist[v] < p.first) { continue; }
        for(int i=0; i<G[v].size(); i++) {
          auto& e = G[v][i];
          if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
            dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
            prevv[e.to] = v;
            preve[e.to] = i;
            pq.emplace(dist[e.to], e.to);
          }
        }
      }
 
      if(dist[t] == inf) { return -1; }
      for(int i=0; i<h.size(); i++) h[i] += dist[i];
 
      int d = f;
      for(int i=t; i!=s; i=prevv[i]) {
        d = min(d, G[prevv[i]][preve[i]].cap);
      }
      f -= d;
      ret += d * h[t];
      for(int i=t; i!=s; i=prevv[i]) {
        auto& e = G[prevv[i]][preve[i]];
        e.cap -= d;
        G[i][e.rev].cap += d;
      }
    }
    return ret;
  }
 
};
 
int main() {
 
  int Tc; cin >> Tc;
  rep(_, Tc) {
    int N; cin >> N;
 
    primal_dual pd(2 * N + 2);
    vector<int> s(N), t(N); vector<ll> w(N);
    rep(i, N) {
      cin >> s[i] >> t[i] >> w[i];
    }
 
    const int SRC = 2 * N, SINK = 2 * N + 1;
 
    rep(i, N) {
      pd.add_edge(2*i, 2*i+1, 1, -w[i]);
      pd.add_edge(SRC, 2*i, 1, 0);
      pd.add_edge(2*i+1, SINK, 1, 0);
    }
 
    rep(i, N) rep(j, N) {
      if(t[i] < s[j]) {
        pd.add_edge(2*i+1, 2*j, inf, 0);
      }
      if(t[j] < s[i]) {
        pd.add_edge(2*j, 2*i+1, inf, 0);
      }
    }
 
    cout << -pd.min_cost_flow(SRC, SINK, 2) << endl;
  }
   
  return 0;
}