首页 > 代码库 > HDU 4085 Peach Blossom Spring 斯坦纳树 状态压缩DP+SPFA

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; }




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