游览计划 bzoj-2595 wc-2008

题目大意：、。

注释：略。

想法：裸题求斯坦纳树。

斯坦纳树有两种转移方式，设$f[s][i]$表示联通状态为$s$，以$i$为根的最小代价。

第一个转移就是$f[s][i]=f[t][i]+f[s-t][i]$。这个显然但是是针对边权的，这个题我们需要减掉多算的点权更新答案。

第二个转移是相同的$s$，即$f[s][i]=f[s][j]+E[i][j]$。

发现很像三角形不等式，用$spfa$转移即可。

代码2595：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define inf 1e9#define N 11 #define M 1050 using namespace std;char *p1,*p2,buf[100000];#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)int rd() {int x=0,f=1; char c=nc(); while(c<48) {if(c=='-') f=-1; c=nc();} while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;}struct Node {int x,y,S;}pre[N][N][M];struct par {int x,y;};int a[N][N],f[N][N][M];int n,m,tot=0;int dic_x[]={0,0,1,-1};int dic_y[]={1,-1,0,0};bool vis[N][N];queue
          
           q;void spfa(int cur){ while(!q.empty()) { par p=q.front(); q.pop(); vis[p.x][p.y]=false; for(int k=0;k<4;k++) { int wx=p.x+dic_x[k],wy=p.y+dic_y[k]; if(wx<1||wx>n||wy<1||wy>m) continue; if(f[wx][wy][cur]>f[p.x][p.y][cur]+a[wx][wy]) { f[wx][wy][cur]=f[p.x][p.y][cur]+a[wx][wy]; pre[wx][wy][cur]=(Node){p.x,p.y,cur}; if(!vis[wx][wy]) vis[wx][wy]=true,q.push((par){wx,wy}); } } }}void dfs(int x,int y,int now){ // printf("%d %d %d\n",x,y,now); vis[x][y]=1; // printf("%d %d %d\n",x,y,now); Node tmp=pre[x][y][now]; // printf("%d %d %d\n",x,y,now); if(!tmp.x&&!tmp.y) return; // printf("%d %d %d\n",x,y,now); dfs(tmp.x,tmp.y,tmp.S); // printf("%d %d %d\n",x,y,now); if(tmp.x==x&&tmp.y==y) dfs(tmp.x,tmp.y,now-tmp.S); // printf("%d %d %d\n",x,y,now);}int main(){ n=rd(),m=rd(); memset(f,0x3f,sizeof f); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { a[i][j]=rd(); if(!a[i][j]) f[i][j][1<

代码5180：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define N 100010 #define M 200010 using namespace std; typedef long long ll;priority_queue
          
           
             >q;int head[N],to[M<<1],nxt[M<<1],tot; ll val[M<<1];ll f[50][N];bool vis[50][N];char *p1,*p2,buf[100000];#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)int rd() {int x=0,f=1; char c=nc(); while(c<48) {if(c=='-') f=-1; c=nc();} while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;}inline void add(int x,int y,ll z) {to[++tot]=y; val[tot]=z; nxt[tot]=head[x]; head[x]=tot;}int main(){ memset(f,0x3f,sizeof f); int n=rd(),k=rd(),m=rd(); for(int i=1;i<=k;i++) {int x=rd(); f[1<<(i-1)][x]=0;} for(int i=1;i<=m;i++) {int x=rd(),y=rd(); ll z=rd(); add(x,y,z),add(y,x,z);} int all=(1<
            
             f[i][x]+val[j]) { f[i][to[j]]=f[i][x]+val[j]; q.push(make_pair(-f[i][to[j]],to[j])); } } } ll ans=0x3f3f3f3f3f3f3f3f; for(int i=1;i<=n;i++) ans=min(ans,f[all][i]); cout << ans << endl ; return 0;}