P4854 MloVtry的咸鱼树状压+最短路

$ \color{#0066ff}{ 题目描述 }$

俗话说种瓜得瓜，种豆得豆，MloVtry把自己砍掉一半埋进了土里，于是它得到了一颗n个点的咸鱼树。

但是问题是由于MloVtry只舍得埋下一半的自己，所以这个咸鱼树是不完整的---甚至它碎裂成了m条边。

作为一条能够致癌的咸鱼，MloVtry当然想要一颗咸鱼树来标榜自己的身份。

MloVtry大概估计出了连接两个点之间的代价，它想知道，最少需要多少代价才能拼出咸鱼树？

值得注意的是，咸鱼树上的咸鱼边们对于MloVtry是很有意见的，所以每条边都会制定一个点集S，只有MloVtry将S这个特殊点集里的所有点都接入某个集合T之后，这条边才可以被加入T这个集合。

MloVtry把脑子埋进了地里，所以这个问题只能由你来解决了。

$\color{#0066ff}{输入格式}$

第一行2个整数n、m

接下来m行，每行4个整数u，v，S，l，表示一条连接u到v的长为l的双向边，要在已经选择了点集S（这个集合用二进制数来表示，1号点对应第1位，其余点同理）之后才能选择。

$\color{#0066ff}{输出格式}$

一行1个整数，表示最小代价。当然，可能存在无解的情况，此时请输出-1。

$\color{#0066ff}{输入样例}$

$\color{#0066ff}{输出样例}$

$\color{#0066ff}{数据范围与提示}$

N<=15,m<=n*(n+10)。

数据保证所有数值在int范围内。

$\color{#0066ff}{题解}$

完美的被题意杀。。。

题目的意思其实是告诉你对于两个状态怎么转移

所以直接状压+最短路就行了

#include<bits/stdc++.h>

#define LL long long

LL in() {

	char ch; LL x = 0, f = 1;

	while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);

	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));

	return x * f;

}

int n, m;

const int maxn = 1005050;

const int inf = 0x7fffffff;

using std::pair;

using std::make_pair;

std::priority_queue<pair<int, int>, std::vector<pair<int, int> >, std::greater<pair<int, int> > > q;

struct node {

	int x, y, zt, val;

}e[maxn];

int dis[maxn];

bool vis[maxn];

int main() {

	n = in(), m = in();

	for(int i = 0; i < (1 << n); i++) dis[i] = inf;

	for(int i = 1; i <= m; i++) {

		e[i].x = in(), e[i].y = in(), e[i].zt = in(), e[i].val = in();

	}

	for(int i = 1; i <= n; i++) {

		dis[1 << (i - 1)] = 0;

		q.push(make_pair(dis[1 << (i - 1)], 1 << (i - 1)));

	}

	while(!q.empty()) {

		int zt = q.top().second; q.pop();

		if(vis[zt]) continue;

		vis[zt] = true;

		for(int i = 1; i <= m; i++) {

			int x = e[i].x, y = e[i].y, now = e[i].zt, val = e[i].val;

			if((now | zt) != zt) continue;

			int a = (zt >> (x - 1)) & 1;

			int b = (zt >> (y - 1)) & 1;

			if(!a && !b) continue;

			int newzt = zt | (1 << (x - 1)) | (1 << (y - 1));

			if(dis[newzt] > dis[zt] + val) q.push(make_pair(dis[newzt] = dis[zt] + val, newzt));

		}

	}

	printf("%d\n", dis[(1 << n) - 1] == inf? -1 : dis[(1 << n) - 1]);

	return 0;

}

巴特西

P4854 MloVtry的咸鱼树状压+最短路

$ \color{#0066ff}{ 题目描述 }$

\(\color{#0066ff}{输入格式}\)

\(\color{#0066ff}{输出格式}\)

\(\color{#0066ff}{输入样例}\)

\(\color{#0066ff}{输出样例}\)

\(\color{#0066ff}{数据范围与提示}\)

\(\color{#0066ff}{题解}\)

完美的被题意杀。。。

题目的意思其实是告诉你对于两个状态怎么转移

所以直接状压+最短路就行了

最新文章

热门文章

巴特西

P4854 MloVtry的咸鱼树 状压+最短路

$ \color{#0066ff}{ 题目描述 }$

\(\color{#0066ff}{输入格式}\)

\(\color{#0066ff}{输出格式}\)

\(\color{#0066ff}{输入样例}\)

\(\color{#0066ff}{输出样例}\)

\(\color{#0066ff}{数据范围与提示}\)

\(\color{#0066ff}{题解}\)

完美的被题意杀。。。

题目的意思其实是告诉你对于两个状态怎么转移

所以直接状压+最短路就行了

最新文章

热门文章

P4854 MloVtry的咸鱼树状压+最短路