【HDU】4848 Wow! Such Conquering! dfs爆捜+強力剪定
Wow! Such Conquering!
Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 131 Accepted Submission(s): 42
Problem Description
There are n Doge Planets in the Doge Space. The conqueror of Doge Space is Super Doge, who is going to inspect his Doge Army on all Doge Planets. The inspection starts from Doge Planet 1 where DOS (Doge Olympic Statue) was built. It takes Super Doge exactly Txy time to travel from Doge Planet x to Doge Planet y. With the ambition of conquering other spaces, he would like to visit all Doge Planets as soon as possible. More specifically, he would like to visit the Doge Planet x at the time no later than Deadlinex. He also wants the sum of all arrival time of each Doge Planet to be as small as possible. You can assume it takes so little time to inspect his Doge Army that we can ignore it.
Input
There are multiple test cases. Please process till EOF. Each test case contains several lines. The first line of each test case contains one integer: n, as mentioned above, the number of Doge Planets. Then follow n lines, each contains n integers, where the y-th integer in the x-th line is Txy . Then follows a single line containing n - 1 integers: Deadline2 to Deadlinen. All numbers are guaranteed to be non-negative integers smaller than or equal to one million. n is guaranteed to be no less than 3 and no more than 30.
Output
If some Deadlines can not be fulfilled, please output “-1” (which means the Super Doge will say “WOW! So Slow! Such delay! Much Anger! . . . ” , but you do not need to output it), else output the minimum sum of all arrival time to each Doge Planet.
Sample Input
Sample Output
Source
2014西安全国招待試合の転送ドア:【HDU】4848 Wow!Such Conquering! タイトルの大意.n個の星があり、番号は1~nから、今は1から他のすべての星にアクセスする必要があります.Txyはxからyまでの時間を表し、n-1個のDeadlineは初めて星に2~nまでの最も遅い時間が与えられたDeadlineを超えてはいけないことを示します.要求内にすべての星にアクセスできるかどうかを聞いて、最小の時間を出力できれば、-1を出力します.(3<=n<=30)入力データの複数組.第1行nはn個の星を表し、次にn行毎にn列を表し、第i行j列のTijはiからjまでの時間を表す.次の行n-1個の数は、Deadline[2]~Deadline[n]を表す.星数が30を超えない以上、本題は検索に剪定を加えることで通過できることを意味する.まずfloydは、2つのポイント間の消費時間(x->yおよびy->xの消費時間が異なる場合があることに注意)を前処理し、次にDFSを行うときは、通過していないポイントを選択するだけで拡大すればよい.そして答えはすべての星が歩き回った後、異なる実行可能な案の最小値です.それでは枝切りをしないと必ずタイムアウトしますが、30^30はどう見ても無理です.どうやって枝を切りますか.現在選択すべき点jと以前のスキームが選択した最後の点iとの間の時間の経過Tijに残りの除去すべき星数(現在選択されているエッジはその後も機能するため)+スキームの前に使用された時間の和tottimeがすでに得られた結果ansより大きい場合、直接スキップすることは容易に考えられる.次に最適解が得られないので,次の点を列挙し続ける.しかし、この枝切りだけでは弱すぎて、提出がタイムアウトします.どうしよう?実はもう一つの超強力な枝切り:シナリオが最後の点をiが歩いていない現在の点jまで歩く時間time+Tij>Deadline[j]を選択した場合、次はどう歩いても解けない(これからDFSを続ける時間は増えるが、すでに1つの星が現在行けないので、その後は必ず行かない)を選択して、前のレベルの列挙iに直接戻ります.これを加えると基本的にOKになりますが、他に何かを加えて最適化すればかなり効率が上がると思います.研究を続ける~コードは以下の通りである.
最后に自分のYYの双方向のチェーン時計版をあげて、大神が使ったのを見てやっと使いたいと思ったのです:
Time Limit: 15000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 131 Accepted Submission(s): 42
Problem Description
There are n Doge Planets in the Doge Space. The conqueror of Doge Space is Super Doge, who is going to inspect his Doge Army on all Doge Planets. The inspection starts from Doge Planet 1 where DOS (Doge Olympic Statue) was built. It takes Super Doge exactly Txy time to travel from Doge Planet x to Doge Planet y. With the ambition of conquering other spaces, he would like to visit all Doge Planets as soon as possible. More specifically, he would like to visit the Doge Planet x at the time no later than Deadlinex. He also wants the sum of all arrival time of each Doge Planet to be as small as possible. You can assume it takes so little time to inspect his Doge Army that we can ignore it.
Input
There are multiple test cases. Please process till EOF. Each test case contains several lines. The first line of each test case contains one integer: n, as mentioned above, the number of Doge Planets. Then follow n lines, each contains n integers, where the y-th integer in the x-th line is Txy . Then follows a single line containing n - 1 integers: Deadline2 to Deadlinen. All numbers are guaranteed to be non-negative integers smaller than or equal to one million. n is guaranteed to be no less than 3 and no more than 30.
Output
If some Deadlines can not be fulfilled, please output “-1” (which means the Super Doge will say “WOW! So Slow! Such delay! Much Anger! . . . ” , but you do not need to output it), else output the minimum sum of all arrival time to each Doge Planet.
Sample Input
4 0 3 8 6 4 0 7 4 7 5 0 2 6 9 3 0 30 8 30 4 0 2 3 3 2 0 3 3 2 3 0 3 2 3 3 0 2 3 3
Sample Output
36 -1
Source
2014西安全国招待試合の転送ドア:【HDU】4848 Wow!Such Conquering! タイトルの大意.n個の星があり、番号は1~nから、今は1から他のすべての星にアクセスする必要があります.Txyはxからyまでの時間を表し、n-1個のDeadlineは初めて星に2~nまでの最も遅い時間が与えられたDeadlineを超えてはいけないことを示します.要求内にすべての星にアクセスできるかどうかを聞いて、最小の時間を出力できれば、-1を出力します.(3<=n<=30)入力データの複数組.第1行nはn個の星を表し、次にn行毎にn列を表し、第i行j列のTijはiからjまでの時間を表す.次の行n-1個の数は、Deadline[2]~Deadline[n]を表す.星数が30を超えない以上、本題は検索に剪定を加えることで通過できることを意味する.まずfloydは、2つのポイント間の消費時間(x->yおよびy->xの消費時間が異なる場合があることに注意)を前処理し、次にDFSを行うときは、通過していないポイントを選択するだけで拡大すればよい.そして答えはすべての星が歩き回った後、異なる実行可能な案の最小値です.それでは枝切りをしないと必ずタイムアウトしますが、30^30はどう見ても無理です.どうやって枝を切りますか.現在選択すべき点jと以前のスキームが選択した最後の点iとの間の時間の経過Tijに残りの除去すべき星数(現在選択されているエッジはその後も機能するため)+スキームの前に使用された時間の和tottimeがすでに得られた結果ansより大きい場合、直接スキップすることは容易に考えられる.次に最適解が得られないので,次の点を列挙し続ける.しかし、この枝切りだけでは弱すぎて、提出がタイムアウトします.どうしよう?実はもう一つの超強力な枝切り:シナリオが最後の点をiが歩いていない現在の点jまで歩く時間time+Tij>Deadline[j]を選択した場合、次はどう歩いても解けない(これからDFSを続ける時間は増えるが、すでに1つの星が現在行けないので、その後は必ず行かない)を選択して、前のレベルの列挙iに直接戻ります.これを加えると基本的にOKになりますが、他に何かを加えて最適化すればかなり効率が上がると思います.研究を続ける~コードは以下の通りである.
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std ;
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define clear( a , x ) memset ( a , x , sizeof a )
const int MAXN = 30 ;
const int INF = 3000000 ;
const int MAXH = 1000000 ;
int n ;
int T[MAXN][MAXN] ;
int Deadline[MAXN] ;
bool vis[MAXN] ;
int ans ;
void dfs ( int u , int cnt , int time , int tottime ) {
if ( !cnt ) {
if ( ans > tottime )
ans = tottime ;
return ;
}
REP ( i , n )
if ( !vis[i] && time + T[u][i] > Deadline[i] )
return ;
REP ( i , n ) {
if ( vis[i] || tottime + cnt * T[u][i] >= ans )
continue ;
vis[i] = 1 ;
dfs ( i , cnt - 1 , time + T[u][i] , tottime + cnt * T[u][i] ) ;
vis[i] = 0 ;
}
}
void work () {
while ( ~scanf ( "%d" , &n ) ) {
clear ( vis , 0 ) ;
ans = INF ;
REP ( i , n )
REP ( j , n )
scanf ( "%d" , &T[i][j] ) ;
REPF ( i , 1 , n - 1 )
scanf ( "%d" , &Deadline[i] ) ;
REP ( k , n )
REP ( i , n )
REP ( j , n )
T[i][j] = min ( T[i][j] , T[i][k] + T[k][j] ) ;
vis[0] = 1 ;
dfs ( 0 , n - 1 , 0 , 0 ) ;
if ( ans == INF )
ans = -1 ;
printf ( "%d
" , ans ) ;
}
}
int main () {
work () ;
return 0 ;
}最后に自分のYYの双方向のチェーン時計版をあげて、大神が使ったのを見てやっと使いたいと思ったのです:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std ;
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define clear( a , x ) memset ( a , x , sizeof a )
#define GO( i ) for ( int i = R[0] ; i ; i = R[i] )
const int MAXN = 30 ;
const int INF = 3000000 ;
const int MAXH = 1000000 ;
int n ;
int T[MAXN][MAXN] ;
int Deadline[MAXN] ;
int ans ;
int R[MAXN + 1] , L[MAXN + 1] ;
void dfs ( int u , int cnt , int time , int tottime ) {
if ( !cnt ) {
if ( ans > tottime )
ans = tottime ;
return ;
}
GO ( i )
if ( time + T[u][i] > Deadline[i] )
return ;
GO ( i ) {
int tmp = tottime + cnt * T[u][i] ;
if ( tmp >= ans )
continue ;
L[R[i]] = L[i] , R[L[i]] = R[i] ;// i
dfs ( i , cnt - 1 , time + T[u][i] , tmp ) ;
L[R[i]] = R[L[i]] = i ;// i
}
}
void work () {
while ( ~scanf ( "%d" , &n ) ) {
ans = INF ;
REP ( i , n )
REP ( j , n )
scanf ( "%d" , &T[i][j] ) ;
REP ( i , n - 1 )
scanf ( "%d" , &Deadline[i + 1] ) ;
REP ( i , n )
R[i] = ( i + 1 ) % n , L[( i + 1 ) % n] = i ;
REP ( k , n )
REP ( i , n )
REP ( j , n )
T[i][j] = min ( T[i][j] , T[i][k] + T[k][j] ) ;
//L[R[1]] = n - 1 , R[L[1]] = 1 ; 1~n， 0~n-1， 1(0) 。
dfs ( 0 , n - 1 , 0 , 0 ) ;
if ( ans == INF )
ans = -1 ;
printf ( "%d
" , ans ) ;
}
}
int main () {
work () ;
return 0 ;
}