# 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;
{
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];
void push(int x,int y,int val)
{
}
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;
{
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()
{
for (int i=1;i<=m;++i)
{
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)
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