AOJ: Volume25-2598 Website Tour

AOJ2598.cpp

// AC (http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1867998)
// 方針
// 1. 閉路で何回も見れるやつを見つけるために強連結成分分解して、閉路の頂点を1頂点としてまとめる
// 2. DAGとして繋がっているそれらの頂点をDFSで探索しながら個数制約付きナップサック問題として計算していく
//    (計算する際、まとめた頂点に1つの頂点しか含まれず、自己辺を含まない場合は高々一回しか見れないことに注意する)
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 10000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
//typedef pair<ll, ll> P;
typedef pair<P, int> PI;
typedef pair<int, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

#define N 103
#define M 1003
int p[N], t[N], k[N];

// ここから強連結成分分解
#define V 103
int v;
vector<int> g[V];
vector<int> rg[V];
int group[V];

vector<int> ord;
bool used[V];
void dfs(int s) {
  used[s] = true;
  rep(i, g[s].size()) {
    int t = g[s][i];
    if(!used[t]) {
      dfs(t);
    }
  }
  ord.push_back(s);
}

void rdfs(int s, int col) {
  group[s] = col;
  used[s] = true;
  rep(i, rg[s].size()) {
    int t = rg[s][i];
    if(!used[t]) {
      rdfs(t, col);
    }
  }
}

int scc() {
  rep(i, v) used[i] = false;
  rep(i, v) {
    if(!used[i]) dfs(i);
  }
  ord.clear();
  rep(i, v) used[i] = false;
  int cnt = 0;
  repr(i, v) {
    int s = ord[i];
    if(!used[s]) rdfs(s, cnt++);
  }
  return cnt;
}
// ここまで強連結成分分解

// 分解後のグラフ再構成用
vector<int> g2[V];
vector<int> rg2[V];
vector<int> els[V];
bool eused[N][N];
bool self[N];

int n, m, ti;

// スライド区間 - 最大値
// これライブラリ化したい
#define W 10005
int deq[W];
ll deqv[W];

// 個数制約付きナップサック問題を再帰的に求める
bool sused[N]; // DPが計算済みかどうか
ll dp[V][W];
void sdfs(int v) {
  if(sused[v]) return;
  sused[v] = true;
  rep(i, ti+1) dp[v][i] = 0;
  // 移動できる各頂点に移動して先に計算
  // 重さjにおける最大値は、各頂点のうちの重さjにおける最大値に一致
  rep(i, g2[v].size()) {
    int to = g2[v][i];
    sdfs(to);
    rep(j, ti+1) dp[v][j] = maxd(dp[to][j], dp[v][j]);
  }
  if(els[v].size() == 1 && !self[v]) {
    // 頂点を１つしか含まない頂点 -> 見れるのは高々一回
    int u = els[v][0];
    repr(j, ti-t[u]+1) {
      dp[v][j+t[u]] = maxd(dp[v][j+t[u]], dp[v][j] + p[u]);
    }
  } else {
    // 頂点を2つ以上含む頂点 -> 閉路であるため、ぐるぐるすれば上限回まで見れる
    // 頂点vに含まれる各頂点uについて、個数制約付きナップサック問題を解く
    rep(i, els[v].size()) {
      int u = els[v][i];

      rep(a, t[u]) {
        int sq = 0, tq = 0;
        for(int j=0; j*t[u]+a <= ti; ++j) {
          ll val = dp[v][j*t[u] + a] - j*p[u];
          while(sq < tq && deqv[tq - 1] <= val) --tq;
          deq[tq] = j;
          deqv[tq++] = val;

          dp[v][j*t[u] + a] = deqv[sq] + j*p[u];
          if(deq[sq] == j - k[u]) ++sq;
        }
      }
    }
  }
}

int main() {
  while(cin >> n >> m >> ti && n+m+ti) {
    rep(i, n) {
      cin >> p[i] >> t[i] >> k[i];
      g[i].clear();
      rg[i].clear();
    }
    rep(i, m) {
      int a, b;
      cin >> a >> b; --a; --b;
      g[a].push_back(b);
      rg[b].push_back(a);
    }

    // 強連結成分分解
    v = n;
    int w = scc();
    // 分解した後で頂点、辺を再構成
    // (自己辺は取り除いておくが、頂点を1つしか含まない頂点では自己辺は必要となるのでとっておく)
    rep(i, w) rep(j, w) eused[i][j] = false;
    rep(i, w) {
      g2[i].clear();
      rg2[i].clear();
      els[i].clear();
      self[i] = false;
      sused[i] = false;
    }
    rep(i, n) {
      int c = group[i];
      els[c].push_back(i);
      rep(j, g[i].size()) {
        int d = group[g[i][j]];
        if(c==d) {
          self[c] = true;
          continue;
        }
        if(eused[c][d]) continue;
        g2[c].push_back(d);
        rg2[d].push_back(c);
        eused[c][d] = true;
      }
    }

    // DAGに対するDFSで個数制約付きナップサック問題を解く
    // 開始地点は入る辺がない頂点から (<- この条件はなくても大丈夫そう)
    ll ans = 0;
    rep(i, w) {
      if(rg2[i].empty()) {
        sdfs(i);
        rep(j, ti+1) {
          ans = maxd(ans, dp[i][j]);
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}