专栏文章

题解：AT_arc078_d [ARC078F] Mole and Abandoned Mine

LLastKismet
AT_arc078_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min4udji
此快照首次捕获于
2025/12/01 20:35
3 个月前
此快照最后确认于
2025/12/01 20:35
3 个月前
查看原文

Sol

刻画一下合法图的状态，不难想到可以视作 1→n1\rightarrow n 的一条简单路径，每个节点外挂一个联通块，各个节点外挂的联通块互不相交。
图状压，f(S,i)f(S,i) 表示已经考虑了 SS 中的点，路径最后一点为 ii 的最大边权和，转移就枚举连通块即可，块是否连通以及块内边权和可以预处理得出。直接这么做可以做到 O(3nn2)O(3^nn^2)，交上去 3.63.6 秒过了。
事实上对每个 SS 预处理其补集子集的最大代价即可做到 O(3nn+2nn2)O(3^nn+2^nn^2)，由于很简单且已经过了且我懒就没写了。下面的代码是 O(3nn2)O(3^nn^2) 的。

Code

CPP
const int N=15;

int n,m;
int g[N][N];
int f[1<<N],e[1<<N],lg[1<<N],h[1<<N][N];

inline void Main(){
	cin>>n>>m;
	int sum=0;
	rep(i,1,m){
		int a,b,c;cin>>a>>b>>c;
		--a,--b;
		g[a][b]=g[b][a]=c;
		sum+=c;
	}
	repl(i,0,n)lg[1<<i]=i;
	repl(s,1,1<<n){
		int i=lg[s&-s];
		e[s]=e[s^1<<i];
		repl(j,0,n)if(s>>j&1)e[s]+=g[i][j];
	}
	repl(s,1,1<<n)for(int t=s-1&s;t;t=t-1&s)f[s]|=(e[s]==e[t]+e[s^t]);
	memset(h,-0x3f,sizeof h);
	repl(s,1,1<<n)if(!f[s]&&(s&1)&&(s>>n-1&1^1))h[s][0]=e[s];
	int S=(1<<n)-1;
	repl(s,1,1<<n)repl(i,0,n)if(s>>i&1)
		for(int t=S-s;t;t=t-1&S-s)if(!f[t])repl(j,0,n)if(g[i][j]&&(t>>j&1))chmax(h[s|t][j],h[s][i]+g[i][j]+e[t]);
	put(sum-h[S][n-1]);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...