bzoj4006 파이프 연결 스탠나 숲 서브셋 Dp

이 문제는 요구가 비교적 높다. 같은 채널의 연결만 하면 된다. (요구가 떨어진 것 같지......233) 그리고 우리는 모든 채널이 어느 집합에 속하는 스탠나 나무를 구해야 한다. 마지막으로 서브집합 Dp로 모든 스탠나 나무를 숲으로 합성해야 한다.
구체적으로 먼저 채널의 집합을 열거한 다음에 이 채널에 속하는 모든 사이트를 굵게 한 다음에 이 사이트들이 하나의 집합을 구성하는 거죠.그리고 스탠나 나무의 방법으로 dp+spfa로 이 집합의 스탠나 나무를 만들 수 있습니다!!!
서브집중 dp는 O(N+M)2^P)로 보고 외계 매거 상태는 O(2^P)로 보이기 때문에 O(N+M)4^P로 바뀌었다.하지만 이 분석은 그다지 엄격하지 않다.송이경(신지현):그래도살 수 있어.
AC 코드는 다음과 같습니다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1000000000
#define N 1005
#define M 6005
using namespace std;

int n,m,p,tot,bin[15],f[1<<10][N],g[1<<10],h[M+5],fst[N],pnt[M],len[M],nxt[M];
struct node{ int x,id; }a[15]; bool bo[N];
void add(int x,int y,int z){
	pnt[++tot]=y; len[tot]=z; nxt[tot]=fst[x]; fst[x]=tot;
}
void solve(int now,int cnt){
	int i,j,k,head,tail;
	for (k=1; k<bin[cnt]; k++){
		head=tail=0;
		memset(bo,1,sizeof(bo));
		for (i=1; i<=n; i++){
			for (j=(k-1)&k; j; j=(j-1)&k)
				f[k][i]=min(f[k][i],f[j][i]+f[k^j][i]);
			if (f[k][i]<inf){ h[++tail]=i; bo[i]=0; }
		}
		while (head!=tail){
			head=head%M+1; int x=h[head],p; bo[x]=1;
			for (p=fst[x]; p; p=nxt[p]){
				int y=pnt[p];
				if (f[k][x]+len[p]<f[k][y]){
					f[k][y]=f[k][x]+len[p];
					if (bo[y]){ bo[y]=0; tail=tail%M+1; h[tail]=y; }
				}
			}
		}
	}
	g[now]=inf;
	for (i=1; i<=n; i++) g[now]=min(g[now],f[bin[cnt]-1][i]);
}
bool cmp(node u,node v){ return u.x<v.x; }
int main(){
	scanf("%d%d%d",&n,&m,&p); int i,j,k;
	bin[0]=1; for (i=1; i<=p; i++) bin[i]=bin[i-1]<<1;
	for (i=1; i<=m; i++){
		int x,y,z; scanf("%d%d%d",&x,&y,&z);
		add(x,y,z); add(y,x,z);
	}
	for (i=1; i<=p; i++) scanf("%d%d",&a[i].x,&a[i].id);
	sort(a+1,a+p+1,cmp);
	int last=-1,cnt=0;
	for (i=1; i<=p; i++){
		if (a[i].x!=last){ last=a[i].x; cnt++; }
		a[i].x=cnt;
	}
	for (i=1; i<bin[cnt]; i++) g[i]=inf;
	for (k=1; k<bin[cnt]; k++){
		int tmp=0;
		for (i=1; i<=p; i++) if (k&bin[a[i].x-1]) tmp++;
		for (i=1; i<bin[tmp]; i++) for (j=1; j<=n; j++) f[i][j]=inf;
		tmp=0;
		for (i=1; i<=p; i++)
			if (k&bin[a[i].x-1]){ f[bin[tmp]][a[i].id]=0; tmp++; }
		solve(k,tmp);
		for (i=(k-1)&k; i; i=(i-1)&k) g[k]=min(g[k],g[i]+g[k^i]);
	}
	printf("%d
",g[bin[cnt]-1]);
	return 0;
}

by lych
2016.3.9