| ||||||||||
| 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