PKU 2288 Islands and Bridges
http://poj.org/problem?id=2288
n個のノードを持つ無向グラフが与えられる。
この時に、ノードごとに得点Viが設定されており、すべてのノードを一度だけ通る経路
c1c2・・・cnがあるときに、その経路の得点はノード単体の得点、経路上で隣り合うノードの得点の積、経路上の連続する3つのノードの両端を結ぶノード間にも辺があればそれら3つのノードの得点の積すべての和となる。
このとき、与えられたグラフ上の経路で得られる最大の得点と、その得点を取るような経路がいくつあるかを答えろというような問題。
ただし、向きが違うだけのものは同じとみなす。
全探索したら、全然通らないようなので、DPしました。
向きが違うだけのものは同じとみなすそうですが、ノードが1個だけの場合は処理を分けないといけないようでした。
あとDP書く時、思った以上にバグりました。
pair<ll,ll> cost[14][14][1<<13]; vector<int> G[20]; int gg[20][20]; int v[20]; int n; void solve(){ int m; cin>>n>>m; memset(cost,0,sizeof(cost)); memset(gg,0,sizeof(gg)); v[n]=0; rep(i,n){ G[i].clear(); cin>>v[i]; } rep(i,m){ int a,b; cin>>a>>b; --a,--b; G[a].pb(b); G[b].pb(a); gg[a][b]=gg[b][a]=1; } cost[n][n][0]=mp(0,1); rep(st,(1<<n)-1){ rep(a,n+1){ if((st&(1<<a))==0 && a!=n)continue; rep(b,n+1){ if((st&(1<<b))==0 && b!=n)continue; if(cost[a][b][st].S==0 || (a!=n && a==b))continue; rep(c,n){ if((st&(1<<c)) || (b!=n && !gg[b][c]))continue; int nst=st|1<<c; ll nsum=cost[a][b][st].F+v[c]+v[c]*v[b]; if(gg[a][c])nsum+=v[a]*v[b]*v[c]; if(cost[b][c][nst].F>nsum)continue; if(cost[b][c][nst].F==nsum)cost[b][c][nst].S+=cost[a][b][st].S; else cost[b][c][nst]=mp(nsum,cost[a][b][st].S); } } } } ll asum=0; ll ans=0; rep(i,n+1)rep(j,n+1){ const PI & co=cost[i][j][(1<<n)-1]; if(asum>co.F)continue; if(asum==co.F)ans+=co.S; else{ asum=co.F; ans=co.S; } } cout<<asum<<' '<<(n-1?ans/2:ans)<<endl; } main(){ int T; cin>>T; while(T--)solve(); }