BZOJ 4006 pipe connection (minimum Steiner tree + pressure DP)

Title Link: BZOJ 4006

Abstract: n points, of which p (P < = 10) are important points and m are undirected edges. P important points are divided into several categories, and the minimum cost of interconnection of important points of the same kind is obtained.

Explain my understanding, not necessarily right.

  • We only need some points to connect and think of the minimum Steiner tree; when we see P < = 10, we think of the shape pressure.

  • Let dp[i][status] indicate that I point is the root of (a certain) minimum Steiner tree, and the points indicated by status indicate the minimum cost of establishing a channel according to the same color of the topic. The final answer is Max {DP [i] [2 ^ P-1]} (1 < = I < = n).

  • And status can represent a minimum Steiner tree, that is, spfa(status) can find dp[i][status], and status can also represent forest, which comes from the subsets of status.

(refer to Some big guy's blog , but it's much worse than big brother's QwQ)
code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
inline int read()
{
    char c=getchar(); int num=0,f=1;
    while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }
    while (c<='9'&&c>='0') { num=num*10+c-'0'; c=getchar(); }
    return num*f;
}
struct edge{
    int to,ne,val; 
}e[100005];
int n,m,tot=0,head[1005],dp[1005][1055];
void push(int x,int y,int val)
{
    e[++tot].to=y; e[tot].val=val; e[tot].ne=head[x]; head[x]=tot;
    e[++tot].to=x; e[tot].val=val; e[tot].ne=head[y]; head[y]=tot;
}
int ans[1055],sum[15],tmp[15],K,S;
bool vis[1005];
struct point{
    int col,w;
}a[15];
bool check(int status)
{
    for (int i=1;i<=10;++i) tmp[i]=0;
    for (int i=1;i<=K;++i)
     if (status&(1<<(i-1))) tmp[a[i].col]++;
    for (int i=1;i<=10;++i)
     if (tmp[i]&&tmp[i]!=sum[i]) return false;
    return true;
}
void spfa(int status)          // Ensure the shortest circuit in status state 
{
    queue<int> q;
    for (int i=1;i<=n;++i) vis[i]=true,q.push(i);
    while (!q.empty())
    {
        int now=q.front(); q.pop();
        vis[now]=false;
        for (int i=head[now];i;i=e[i].ne)
        {
            int v=e[i].to;
            if (dp[v][status]>dp[now][status]+e[i].val)
            {
                dp[v][status]=dp[now][status]+e[i].val;
                if (!vis[v]) vis[v]=true,q.push(v);
            }
        }   
    }
}
int main()
{
    n=read(); m=read(); K=read();
    for (int i=1;i<=m;++i)
    {
        int x=read(),y=read(),z=read();
        push(x,y,z);
    }
    S=1<<K;
    for (int i=1;i<=n;++i)
     for (int j=0;j<S;++j)
      dp[i][j]=inf;               
    for (int s=0;s<S;++s) ans[s]=inf;                // Initialize inf 

    for (int i=1;i<=K;++i) 
     a[i].col=read(),a[i].w=read(),sum[a[i].col]++;
    for (int i=1;i<=K;++i)
     dp[a[i].w][1<<(i-1)]=0;                // Initial value 
    for (int s=0;s<S;++s)             // All States 
    {
        for (int i=1;i<=n;++i)
         for (int s0=s;s0;s0=(s0-1)&s)
          dp[i][s]=min(dp[i][s],dp[i][s0]+dp[i][s^s0]);             // Transfer from subset 
        spfa(s);                       // Shortest circuit in the same state 
    }
    for (int s=0;s<S;++s)               
     for (int i=1;i<=n;++i)
      ans[s]=min(ans[s],dp[i][s]);                 // Minimum value in a state 
    for (int s=0;s<S;++s)           // All legal status 
     if (check(s)) for (int s0=s;s0;s0=(s0-1)&s)       // All legal subsets            
      if (check(s0)) ans[s]=min(ans[s],ans[s0]+ans[s^s0]);           // Spell out the minimum answer 
    printf("%d",ans[S-1]);
    return 0;
}

Posted on Mon, 04 May 2020 02:57:43 -0700 by drfate