@codeforces - 1149D@ Abandoning Roads

@description@
@solution@
@accepted code@
@details@

@description@

给定一个 n 点 m 条边的无向连通图，每条边的边权为 a 或 b。

对于 1 ~ n 中的每一个 i，求在所有可能的最小生成树中 1 -> i 的最短路的最小值。

Input

第一行包含 4 个整数 n, m, a 与 b (2≤n≤70, n−1≤m≤200, 1≤a<b≤10^7)

接下来 m 行，每行三个整数 u, v, c (1≤u,v≤n, u≠v, c∈{a,b}) 描述了一条带权边 (u, v)，其权值为 c。

图连通且无自环重边。

Output

输出一行 n 个整数，第 p 个描述了从 1 到 p 的可能最小值。

Examples

Input

5 5 20 25

1 2 25

2 3 25

3 4 20

4 5 20

5 1 20

Output

0 25 60 40 20

Input

6 7 13 22

1 2 13

2 3 13

1 4 22

3 4 13

4 5 13

5 6 13

6 1 13

Output

0 13 26 39 26 13

@solution@

感觉这道题有一点乱搞.jpg。

考虑 kruskal 求最小生成树的过程：把边按从小到大的顺序尝试加入。

这道题只有两种边权，所以一定是先用边权为 a 的边构成一个森林，再用边权为 b 的边连接这些森林。

一个最短路满足什么条件时不合法？

稍微动手画一画，发现边权为 a 的边并不会影响合法性（可以通过破圈法证明一条简单路径上的 a 边可以同时存在于最小生成树之中）。

不合法的情况只可能因为有些边权为 b 的边不能同时共存于最小生成树中。

什么时候边权为 b 的边不能同时共存？

再联系到我们 kruskal 的过程：假如将 a 边连接的连通块缩点，这些 b 边如果在缩点后的图上形成了环就不合法。

即我们走 b 边不能在以前经过的结点。

状压？但是这是 2^70 啊。

注意到单个结点用不着状压，那么复杂度降到 2^35。

还是很大？继续。2 个结点与 3 个结点也不需要状压：假如形成了环，则可以经过 2 条 b 边从 u -> p -> v。

然而我们内部的 a 边 <= 2 条，走这个内部的 a 边肯定比绕外部的 b 边短，所以最短路不会绕外面。

只有 >= 4 的连通块需要状压，状压部分的复杂度降成 2^17，够了。

那么再套一个 dijkstra 的复杂度，总复杂度为 O(2^(n/4)*m*log(m))。官方题解好像可以更快来着。

不过这个复杂度足够通过本题了。

@accepted code@

#include <cstdio>

#include <queue>

using namespace std;

const int MAXN = 70;

const int MAXM = 200;

const int INF = int(1E9);

struct edge{

	int to, dis;

	edge *nxt;

}edges[2*MAXM + 5], *adj[MAXN + 5], *ecnt = edges;

void addedge(int u, int v, int w) {

	edge *p = (++ecnt);

	p->to = v, p->dis = w, p->nxt = adj[u], adj[u] = p;

	p = (++ecnt);

	p->to = u, p->dis = w, p->nxt = adj[v], adj[v] = p;

}

struct node{

	int d, s, x;

	node(int _d=0, int _s=0, int _x=0) : d(_d), s(_s), x(_x) {}

	friend bool operator < (node a, node b) {

		return a.d > b.d;

	}

};

bool vis[MAXN][1<<17];

int d[MAXN][1<<17];

priority_queue<node>que;

int dis[MAXN + 5], fa[MAXN + 5], siz[MAXN + 5];

int find(int x) {

	return fa[x] = (fa[x] == x ? x : find(fa[x]));

}

void unite(int x, int y) {

	int fx = find(x), fy = find(y);

	if( fx != fy ) fa[fx] = fy, siz[fy] += siz[fx];

}

int id[MAXN + 5], cnt, tot;

int u[MAXM + 5], v[MAXM + 5], w[MAXM + 5];

int n, m, a, b;

int main() {

	scanf("%d%d%d%d", &n, &m, &a, &b);

	for(int i=0;i<n;i++) fa[i] = i, siz[i] = 1;

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

		scanf("%d%d%d", &u[i], &v[i], &w[i]), u[i]--, v[i]--;

		if( w[i] == a )

			addedge(u[i], v[i], w[i]), unite(u[i], v[i]);

	}

	for(int i=0;i<n;i++)

		if( find(i) == i ) {

			if( siz[i] >= 4 ) id[i] = (cnt++);

			else id[i] = -1;

		}

	for(int i=0;i<n;i++)

		id[i] = id[find(i)];

	tot = (1<<cnt);

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

		for(int s=0;s<tot;s++)

			d[i][s] = INF;

		dis[i] = INF;

	}

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

		if( w[i] == b && find(u[i]) != find(v[i]) )

			addedge(u[i], v[i], w[i]);

	que.push(node(0, 0, 0));

	while( !que.empty() ) {

		node x = que.top(); que.pop();

		if( vis[x.x][x.s] ) continue;

		dis[x.x] = min(dis[x.x], x.d);

		vis[x.x][x.s] = true;

		for(edge *p=adj[x.x];p;p=p->nxt) {

			if( p->dis == a && x.d + p->dis < d[p->to][x.s] )

				que.push(node(d[p->to][x.s]=x.d+p->dis, x.s, p->to));

			else if( id[p->to] == -1 || !((x.s >> id[p->to]) & 1) ) {

				int s = (x.s | (id[x.x] == -1 ? 0 : (1<<id[x.x])));

				if( x.d + p->dis < d[p->to][s] )

					que.push(node(d[p->to][s]=x.d+p->dis, s, p->to));

			}

		}

	}

	for(int i=0;i<n;i++)

		printf("%d%c", dis[i], (i == n - 1 ? '\n' : ' '));

}

@details@

n <= 70 你以为是什么多项式算法。

其实这道题是一个 np 问题 2333。

巴特西

@codeforces - 1149D@ Abandoning Roads

@description@

@solution@

@accepted code@

@details@

最新文章

热门文章