「CF852D」Exploration Plan

题目描述

给定一张 \(V\) 个点，\(M\) 条边的边带权无向图，有 \(N\) 个人分布在图上的点上，第 \(i\) 个人在 \(x_i\) 这个点上，定义从一个点走到另一个点的时间为所走的路径上所有边权之和，问至少过多久才可以满足至少有 \(K\) 个点上有人。

数据范围：

\(1\le V \le600,1\le E \le 20000,1\le N \le\min(V,200),1\le K \le N\)

基本思路

首先可以二分答案。

对于当前二分到的 \(mid\)，我们对于每一个人，都向他可以去到的点连一条边（路径的最短距离可以用 \(\text{Floyd}\) 预处理一下)，然后直接跑二分图最大匹配就好了。

细节注意事项

记得判无解

参考代码

/*--------------------------------

  Author: The Ace Bee

  Blog: www.cnblogs.com/zsbzsb

  This code is made by The Ace Bee

--------------------------------*/

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#include <queue>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= (c == '-'), c = getchar();

	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

	s = f ? -s : s;

}

const int _ = 700;

const int INF = 2147483647;

int n, m, p, k, x[_];

int dis[_][_], vis[_], bel[_], g[_][_];

inline int dfs(int u) {

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

		if (vis[i] || !g[u][i]) continue;

		vis[i] = 1;

		if (bel[i] == 0 || dfs(bel[i]))

			return bel[i] = u, 1;

	}

	return 0;

}

inline bool check(int mid) {

	memset(g, 0, sizeof g);

	for (rg int i = 1; i <= p; ++i)

		for (rg int j = 1; j <= n; ++j)

			g[i][j] = (int) dis[x[i]][j] <= mid;

	int res = 0;

	memset(bel, 0, sizeof bel);

	for (rg int i = 1; i <= p; ++i)

		memset(vis, 0, sizeof vis), res += dfs(i);

	return res >= k;

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	read(n), read(m), read(p), read(k);

	for (rg int i = 1; i <= p; ++i) read(x[i]);

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

		for (rg int j = 1; j <= n; ++j)

			dis[i][j] = 1e9;

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

	for (rg int u, v, d, i = 1; i <= m; ++i) {

		read(u), read(v), read(d);

		dis[v][u] = dis[u][v] = min(dis[u][v], d);

	}

	for (rg int k = 1; k <= n; ++k)

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

			for (rg int j = 1; j <= n; ++j)

				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

	int l = 0, r = 1731311 + 1;

	while (l < r) {

		int mid = (l + r) >> 1;

		if (check(mid)) r = mid;

		else l = mid + 1;

	}

	if (l > 1731311) puts("-1");

	else printf("%d\n", l);

	return 0;

}

完结撒花 \(qwq\)

巴特西

「CF852D」Exploration Plan

题目描述

基本思路

细节注意事项

参考代码

最新文章

热门文章