Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
注意只有一个点的情况。In Reply To:求解啊 wa得快吐了,,, Posted by:zwliu at 2012-12-17 23:37:01 > 求大神指导 这程序哪里错了 > #include <iostream> > #include <cstdio> > #include <cstring> > #include <cmath> > #include <algorithm> > > using namespace std; > > typedef long long ll; > const int INF = ~0u>>1; > const int maxn = 14; > int n, m; > ll dp[1<<maxn][maxn][maxn]; > bool mm[maxn][maxn]; > //dp[s][i][j] = max(dp[ss][k][i]+v[j]+v[i]*v[j]+mm[k][j]?v[i]*v[j]*v[k]: 0 ); > > ll v[maxn]; > > void solve(){ > if( n == 1 ) { > printf("%lld 1\n", v[1]); return ; > } > > int M = 1<<n; > ll num = 0, maxx = -1; > for ( int i=1; i<M; ++i ) > for ( int j=1; j<=n; ++j ) > for ( int k=1; k<=n; ++k ) > dp[i][j][k] = -INF; > for ( int i=1; i<=n; ++i ) > for ( int j=1; j<=n; ++j ) if(mm[i][j] && i^j) > { > int s = (1<<(i-1)) +(1<<(j-1)); > dp[s][i][j] = v[i]+v[j]+v[i]*v[j]; > if( s == M-1 ) { > if(dp[s][i][j] > maxx) { maxx = dp[s][i][j]; num=1; } > else if(dp[s][i][j] == maxx) ++num; > } > } > > for ( int s=1; s<M; ++s ) { > int i, j; > for ( i=1; i<=n; ++i ) if(s&(1<<(i-1) ) ) > { > for ( j=1; j<=n; ++j ) if( ( s&(1<<(j-1) ) ) && i^j ) > { > if(dp[s][i][j] == -INF ) continue; > for ( int k=0; k<n; ++k ) > { > if(s & (1<<k) ) continue; > int news = s+ (1<<k ); > if( mm[j][k+1] == 0 ) continue; > ll tmp = dp[s][i][j]+ v[k+1]+ v[j]*v[k+1]; > tmp += mm[k+1][i]?v[i]*v[j]*v[k+1]:0; > // cout<< s <<" news " << news <<" "<< dp[s][i][j]<<" " << tmp << endl; > if(news == M-1 ) { > if(tmp > maxx ){ maxx = tmp; num=1; } > else if(tmp == maxx) ++num; > } > if(dp[news][j][k+1] < tmp ) { > dp[news][j][k+1] = tmp; > } > } > } > } > } > if(maxx >= 0) > cout << maxx <<' ' << num/2 << '\n'; > else puts("0 0"); > }; > > int main( ){ > //freopen("out.txt", "r", stdin); > // freopen("input.txt", "w", stdout); > int T; scanf ("%d", &T); > while( T-- ) { > scanf ("%d%d", &n, &m); > memset (mm, 0, sizeof mm); > for ( int i=1; i<=n; ++i ) scanf ("%lld", &v[i]); > for ( int i=0, a, b; i<m; ++i ) { > scanf ("%d%d", &a, &b); > mm[a][b] = mm[b][a] = true; > } > solve(); > } > }; > /** > 8 > 3 3 > 2 2 2 > 1 2 > 2 3 > 3 1 > > 4 6 > 1 2 3 4 > 1 2 > 1 3 > 1 4 > 2 3 > 2 4 > 3 4 > > */ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator