POJ3229
題意:n(n<=15)個のノードの重み付き無方向図を与え、辺権はこの辺を通過した時間、点権はこの点に滞在した時間である.m個の点(m<=n)を与え、これらの点は通過しなければならない.始点は1番で、終点は1番に戻らなければなりません.Tを与えて、T時間内に題意の経路の上で通過することを求めます
最も多い点の数.
解析:これは図上の状圧DPである.すでに観光した各ポイントは1で、観光していないものは0で表示されます.ある時点の遊覧状態は整数のバイナリ形式で表すことができ、これは状圧を採用する原因である.定義状態f(i,j)は、i番目の点まで歩いたとき、歩いた点の状態がjのときにかかる時間の量である.f(i,j)=min(f(i,j),f(k,j−(1<注意:国人はBを装って英語で出題して、私を殺しました.第一に、1つの点を通って、必ずしもここで止まる必要はありません.もちろん、この点はansに含まれません.第二に、テーマ叙述に問題があるところを赤で修正した.第三に、この人は1日に12時間かけて旅行しますが、もし彼が20時間かけて道にいるならば、それは彼が1日に多くの旅行の時間を費やして、もし彼が景色を鑑賞して半分の当日の12時間が終わったら、彼は明日引き続き鑑賞します(寝ている間に車に間に合わないでしょう).
注意:状圧はメモリを節約するので、0番から、彼が与えたノード番号はすべて-1です.また中には除法があり、除算が尽きず、doubleで保存されています.
コードは以下に示す
最も多い点の数.
解析:これは図上の状圧DPである.すでに観光した各ポイントは1で、観光していないものは0で表示されます.ある時点の遊覧状態は整数のバイナリ形式で表すことができ、これは状圧を採用する原因である.定義状態f(i,j)は、i番目の点まで歩いたとき、歩いた点の状態がjのときにかかる時間の量である.f(i,j)=min(f(i,j),f(k,j−(1<
注意:状圧はメモリを節約するので、0番から、彼が与えたノード番号はすべて-1です.また中には除法があり、除算が尽きず、doubleで保存されています.
コードは以下に示す
#include<algorithm>
#include<cstdio>
using namespace std;
const double inf = 1e9;
int n, m, d, st = 0,ans = -1,u,v,dis,op;
double f[16][1<<16],a[16],map[16][16];
//a ,map
int main()
{
while(scanf("%d%d%d",&n,&m,&d) &&(n||m||d) )
{
int temp;
double day = d * 12.0;
st = 0,ans = -1; //st
for(int i = 0; i < n; ++i) //
{
for(int j = 0; j < 1<<n; ++j)
f[i][j]=inf;
for(int j = 0; j < n; ++j)
map[i][j]=inf;
map[i][i]=0.0;
}
for(int i = 0; i < m; ++i)
{
scanf("%d",&temp) ;
st += 1<<(temp-1) ; //
}
for(int i = 0; i < n; ++i) scanf("%lf", &a[i]) ;
double t;
while(scanf("%d%d%d%d",&u,&v,&dis,&op) &&(u||v||dis||op))
{
u--,v--; // -1
t = dis*1.0;
if(op) t /= 120.0;
else t /= 80.0;
map[u][v] = map[v][u] = min(map[u][v], min(map[v][u], t)) ; // , a b bus train
}
for(int k = 0; k < n; ++k)
for(int i = 0; i < n; ++i)
if(i != k)
for(int j = 0; j < n; ++j)
if(j != k)
map[i][j] = min(map[i][j],map[i][k]+map[k][j]) ;
for(int i = 1; i < n; ++i) // 1 f
f[i][1<<i]=map[i][0]+a[i];
for(int j = 0; j < 1<<n; ++j) //dp
for(int i = 0; i < n; ++i)
{
if(j&(1<<i) &&(1<<i) !=j) //dp
for(int k = 0; k < n; ++k) if(j&(1<<k) &&(1<<k) !=j&&i != k) //dp
f[i][j]=min(f[i][j],f[k][j-(1<<i) ]+map[k][i]+a[i]) ;
if((j&st) == st && f[i][j]+map[i][0] <= day) //
{
int temp = j,cnt = 0;
while(temp) //
{
if(temp&1) cnt++;
temp >>= 1;
}
ans = max(ans, cnt) ;
}
}
if(ans >= 0) printf("%d
",ans) ;
else printf("No Solution
") ;
}
}