HDU 4085 Peach Blossom Spring 斯坦纳树 状态压缩DP+SPFA

状态压缩dp+spfa解斯坦纳树

枚举子树的形态 dp[i][j] = min(dp[i][j], dp[i][k]+dp[i][l]) 当中k和l是对j的一个划分

依照边进行松弛 dp[i][j] = min(dp[i][j], dp[i'][j]+w[i][j])当中i和i'之间有边相连

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

const int maxn = 55;

const int maxm = 1010;

const int INF = 9999999;

int n, m, k;

int d[maxn][maxn];

int dp[1<<16][maxn], dp2[1<<16], a[1<<16];

int inq[1<<16][maxn];

int first[maxn], cnt;

struct node

{

	int v, w, next;

}e[2222];

struct edge

{

	int u, v, w;

	edge(){}

	edge(int u, int v, int w): u(u), v(v), w(w) {}

};

queue <edge> Q;

void spfa()

{

	while(!Q.empty())

	{

		edge x = Q.front(); Q.pop();

		int u = x.u, v = x.v;

		inq[u][v] = 0;

		for(int i = 0; i < n; i++)

		{

			if(d[v][i] != -1)

			{

				if(dp[u|a[i]][i] > dp[u][v] + d[v][i])

				{

					dp[u|a[i]][i] = dp[u][v] + d[v][i];

					if(!inq[u|a[i]][i] && (u|a[i]) == u)

					{

						inq[u|a[i]][i] = 1;

						Q.push(edge(u|a[i], i, dp[u|a[i]][i]));

					}

				}

			}

		}

	}

}

bool ok(int x)

{

    int ans = 0;

    for(int i = 0; x; i++, x >>= 1)

        ans += (x&1)*(i < k ?

1 : -1);

    return ans == 0;

}

void floyd()

{

	for(int l = 0; l < n; l++)

		for(int i = 0; i < n; i++)

			for(int j = 0; j < n; j++)

				if(d[i][l] != -1 && d[l][j] != -1)

					if(d[i][j] == -1 || d[i][j] > d[i][l]+d[l][j])

						d[i][j] = d[i][l]+d[l][j];

}

void steiner()

{

	int all = (1<<(2*k));

	for(int i = 0; i < all; i++)

		for(int j = 0; j < n; j++)

			dp[i][j] = INF;

	memset(a, 0, sizeof(a));

	for(int i = 0; i < k; i++)

		a[i] = (1<<i), dp[(1<<i)][i] = 0;

	for(int i = k; i < 2*k; i++)

		a[n-2*k+i] = (1<<i), dp[(1<<i)][n-2*k+i] = 0;

	for(int s = 1; s < all; s++)

	{

		for(int i = 0; i < n; i++)

		{

			for(int s0 = (s-1)&s; s0; s0 = (s0-1)&s)

			{

				dp[s][i] = min(dp[s][i], dp[s0|a[i]][i]+dp[(s^s0)|a[i]][i]);

			}

			if(dp[s][i] < INF)

			{

				Q.push(edge(s, i, dp[s][i]));

				inq[s][i] = 1;

			}

		}

		spfa();

	}

	for(int i = 0; i < all; i++)

	{

		dp2[i] = INF;

		for(int j = 0; j < n; j++)

			dp2[i] = min(dp2[i], dp[i][j]);

	}

	for(int i = 1; i < all; i++)

	{

		if(ok(i))

		{

			for(int s = (i-1)&i; s; s = (s-1)&i)

			{

				if(ok(i^s))

					dp2[i] = min(dp2[i], dp2[s]+dp2[i^s]);

			}

		}

	}

	if(dp2[all-1] == INF)

		puts("No solution");

	else

		printf("%d\n", dp2[all-1]);

}

int main()

{

	int T;

	scanf("%d", &T);

	while(T--)

	{

		scanf("%d %d %d", &n, &m, &k);

		memset(d, -1, sizeof(d));

		for(int i = 0; i < m; i++)

		{

			int x, y, z;

			scanf("%d %d %d", &x, &y, &z);

			x--, y--;

			if(d[x][y] == -1 || d[x][y] > z)

				d[x][y] = d[y][x] = z;

		}

		floyd();

		steiner();

	}

	return 0;

}