[loj3302]信号传递

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,t,x,y,a[105][105],f[10000005],g[105];
 4 int main(){
 5     scanf("%d%d%d",&m,&n,&t);
 6     for(int i=1;i<=m;i++){
 7         scanf("%d",&y);
 8         y--;
 9         if (i>1)a[x][y]++;
10         x=y;
11     }
12     for(int i=0;i<n;i++)a[i][i]=0;
13     memset(f,0x3f,sizeof(f));
14     f[0]=0;
15     for(int i=0;i<(1<<n);i++){
16         int s=1,l=i-(i&(i-1));
17         for(int j=0;j<n;j++)s+=((i&(1<<j))>0);
18         for(int j=0;(1<<j)<=l;j++)
19             for(int k=0;k<n;k++)
20                 g[k]=g[k]+(t*a[k][j]+a[j][k]+a[k][j]-t*a[j][k])*(1-2*((1<<j)<l));
21         if (!l)l=(1<<n);
22         for(int j=0;(1<<j)<=l;j++){
23             g[j]=0;
24             if ((1<<j)<l)
25                 for(int k=0;k<n;k++)
26                     if ((i&(1<<k))==0)g[j]+=t*a[k][j]-a[j][k];
27                     else g[j]+=t*a[j][k]+a[k][j];
28         }
29         for(int j=0;j<n;j++)
30             if ((i&(1<<j))==0)f[i|(1<<j)]=min(f[i|(1<<j)],f[i]+s*g[j]);
31     }
32     printf("%d",f[(1<<n)-1]);
33 }