Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

注意只有一个点的情况。

Posted by yygy at 2013-01-26 19:27:34 on Problem 2288
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator