自动搬运

查看原文

来自洛谷，原作者为

	JZYshuraK **

搬运于2025-08-24 22:04:36，当前版本为作者最后更新于2019-07-06 08:54:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

没人写题解我就胡一个吧

这个题真的是.....一言难尽

首先先明确一下题意：

要求一个最小生成树，其中每条边有选取条件$S$，当$S$代表的所有点连通时，这条边才能被选。

不保证$S$包含这条边的两个端点.....

这太自闭了.....

意识到这个情况直接$A$，意识不到就剩$10$分/xk

由于$n$非常小，不难想到状压。

设$f[S]$表示使得$S$代表的所有点连通的最小代价

考虑从$S$往外转移，边$j$可以往外转移需要满足$S \& e[j].S == e[j].S$

然后再判一下，$S$是不是至少包含着边$j$的一个端点即可。

$Code:$

#include <bits/stdc++.h>
#define N 20 
using namespace std;
int bin[N];
int f[33000];
struct Edge{int x,y,S,z;}e[N*N];
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {int x=0,f=1; char c=nc(); while(c<48) {if(c=='-') f=-1; c=nc();} while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;}
int main()
{
	int n=rd(),m=rd();
	bin[1]=1; for(int i=2;i<=n;i++) bin[i]=bin[i-1]<<1;
	for(int i=1;i<=m;i++)
	{
		e[i].x=rd(),e[i].y=rd(),e[i].S=rd(),e[i].z=rd();
	}
	int all=(1<<n)-1;
	memset(f,0x3f,sizeof f);
	f[0]=0;
	for(int i=1;i<=n;i++) f[bin[i]] = 0;
	for(int i=0;i<=all;i++)
	{
		// f[i] ->
		for(int j=1;j<=m;j++)
		{
			if((i & e[j].S) == e[j].S)
			{
				if(((i & bin[e[j].x]) == bin[e[j].x]) || ((i & bin[e[j].y]) == bin[e[j].y]))
				{
					f[i | (bin[e[j].x] | bin[e[j].y])] = min(f[i] + e[j].z , f[i | (bin[e[j].x] | bin[e[j].y])]);
				}
			}
		}
	}
	if(f[all]==0x3f3f3f3f) puts("-1");
	else cout << f[all] << endl ;
	return 0;
}

我也不知道为啥这个题是个黑题.....

推销个人Blog