保存されている過去のバージョンの一覧

2015年01月11日08時46分12秒

yukicoder No.119 - 旅行のツアーの問題

Source

ニコニコミュニティ
問題文

問題概要

$N$ 個の国があり，自由にいくつかの国を選び訪れる．
その際，番号の若い順に訪れることにして，国に訪れるなら，その国に関する観光ツアーに参加するかどうかを選ぶことができる．
（つまり，各国に対して，行かない，行くけど観光ツアーには参加しない，行って観光ツアーに参加するという $3$ つの選択肢がある）
国 $k$ において，観光ツアーに参加した場合に得られる満足度は $B_k$，観光ツアーに参加しなかったが訪れた場合に得られる満足度は $C_k$ で，国に訪れなかった場合は満足度を得られない．
ここで，$B_k$ より $C_k$ が大きいことも，$C_k$ より $B_k$ が大きいこともあり得る．
また，$M$ 個の関係 $(D_k,E_k), \;\; D_k < E_k$ が与えられ，国 $D_k$ と $E_k$ と両方訪れ，かつ，国 $D_k$ で観光ツアーに参加した場合は，必ず，国 $E_k$ でも観光ツアーに参加しなければならないというものである．
得られる満足度の和の最大値を求める問題．

解法

最小カットに帰着させ，最大流で解く．
まず，各国に対して $B_k+C_k$ の満足度を得られると仮定しておいて，ここから得られることができない満足度の損失を最小化する．
つまり，観光ツアーに参加すれば $C_k$ の損失，参加しなければ $B_k$ の損失，訪れなければ $B_k+C_k$ の損失とする．
グラフは $2N+2$ ノードからなり，形は，始点 - 国X - 国Y - 終点，という感じ．
各国 $k$ に対して，国X，国Yに $1$ つずつノードを作る．このノードを便宜上 $X_k, Y_k$ と呼ぶ．
始点から $X_k$ に張る枝を切ることは，国 $k$ でツアーに参加するのを諦めるという意味で流量 $B_k$ とし，
$Y_k$ から終点に張る枝を切ることは，国 $k$ でツアーに参加せず訪れるのを諦めるという意味で流量 $C_k$ とする．
（ある国に訪れることすらしないというのは，両方の枝が切られることに対応する）
後は，国Xと国Yのノード間には，国 $a$ でツアーに参加したら，国 $b$ でツアーに参加せずに訪れることは許されない（$a=b$ の場合も含む）という関係のある場所に流量無限大の枝を張れば良い．

以下は全探索しており，時間計算量が見積もれない（荒く見積もれば $O(2^N)$）が，通ったもの．
この全探索では番号の小さい国からどうするかを決めていく．
各国に対して，取りうる行動は $3$ パターンあるが，訪れても観光ツアーに参加しなくても良い場合は訪れないという選択肢は考えなくて良いし，訪れれば観光ツアーに参加しなければいけない場合は訪れるだけという選択ができないので，常に $2$ 択なので $O(2^N)$．
また，観光ツアーに参加しない場合が，観光ツアーに参加するより満足度が高いなら観光ツアーに参加することを考えなくて良いし，観光ツアーの満足度の方が満足度が高く，観光ツアーに参加しても，後に訪れる国で新しく観光ツアーを強制される国が増えなければ観光ツアーに問答無用で参加すれば良いので，実際はもっと選択肢は狭い．
また，深さ優先探索で，局所的に満足度が高くなる方を先に選択し，各ステップでこれ以降に得られる満足度の上限を見積もり適当に枝刈りを行っている．
想定解法なら $N$ がもっともっと大きくても解けるが，$N$ が $40$ 程度までしかなく，この記事を書いている現在のテストケースなら一瞬で終わる．

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}

int N;
int B[44], C[44], BC[44];
int M;
int D[11111], E[11111];
ll edge[44];

int res;
int sum[50];

void solve(int depth, ll mask, int gain){
  int i, j, k, lim;

  lim = gain;
  REP(i,depth,N){
    if(mask & 1LL<<i) lim += B[i]; else lim += BC[i];
  }
  if(lim <= res) return;

  if(depth==N){
    res = max(res,gain);
    return;
  }

  if(mask & 1LL<<depth){
    solve(depth+1, mask|edge[depth], gain+B[depth]);
    if(mask != (mask|edge[depth])) solve(depth+1, mask, gain);
  } else {
    if(C[depth]==BC[depth]){
      solve(depth+1, mask, gain+BC[depth]);
    } else {
      solve(depth+1, mask|edge[depth], gain+B[depth]);
      if(mask != (mask|edge[depth])) solve(depth+1, mask, gain+C[depth]);
    }
  }
}

int main(){
  int i, j, k;

  reader(&N);
  rep(i,N) reader(B+i,C+i);
  reader(&M);
  rep(i,M) reader(D+i,E+i);
  rep(i,M) edge[D[i]] |= (1LL<<E[i]);

  rep(i,N) BC[i] = max(B[i],C[i]);
  
  solve(0, 0, 0);
  writerLn(res);

  return 0;
}

Current time: 2024年04月19日14時25分01秒
Last modified: 2015年01月11日08時46分12秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：