CF1100E Andrew and Taxi 二分答案+拓扑排序

\(\color{#0066ff}{ 题目描述 }\)

给定一个有向图，改变其中某些边的方向，它将成为一个有向无环图。

现在求一个改变边方向的方案，使得所选边边权的最大值最小。

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

点数n，边数m，接下来是m条有向边

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

输出一个最大值，一个k

接下来一行k个数，表示那些边需要反向

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

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

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

\(2 \leq n \leq 100000\), \(1 \leq m \leq 100000\)

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

根据题目，显然要二分答案

考虑二分答案之后怎么做

对于比mid大的边，我们肯定是不能改变方向的

于是直接加入图中

然后只需看看有没有环就行了，因为比mid小的边我们可以任意更改

可以用拓扑排序做

因为它只让最大值最小，并没有说改变边的数量最小，所以小的边随便改

现在考虑输出方案

我们在拓扑排序的时候记一下每个点的拓扑序

考虑一条边x到y，如果x的拓扑序大于y，显然可能成环（不是一定成环）

但是如果x的拓扑序小于y，一定不会成环

题目有不限制改边数量，我们就将其反向即可

#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;

}

const int maxn = 1e5 + 10;

struct node {

	int x, y, z, id;

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

		return a.z < b.z;

	}

}e[maxn];

struct E {

	int to;

	E *nxt;

	E(int to = 0, E *nxt = NULL): to(to), nxt(nxt) {}

}pool[maxn], *tail;

int du[maxn], top[maxn];

bool vis[maxn];

int n, m;

E *head[maxn];

void add(int from, int to) {

	head[from] = new E(to, head[from]);

}

bool ok(int mid) {

	std::queue<int> q;

	int cnt = 0;

	tail = pool;

	for(int i = 1; i <= n; i++) du[i] = 0, head[i] = NULL, top[i] = 0;

	for(int i = 1; i <= m; i++) vis[i] = false;

	for(int i = m; i >= 1; i--) {

		if(e[i].z <= mid) break;

		add(e[i].x, e[i].y);

		du[e[i].y]++;

	}

	for(int i = 1; i <= n; i++) if(!du[i]) q.push(i);

	while(!q.empty()) {

		int tp = q.front(); q.pop();

		top[tp] = ++cnt;

		for(E *i = head[tp]; i; i = i->nxt) {

			du[i->to]--;

			if(!du[i->to]) q.push(i->to);

		}

	}

	if(cnt != n) return false;

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

		if(e[i].z > mid) break;

		if(top[e[i].x] > top[e[i].y]) vis[e[i].id] = true;

	}

	return true;

}

int main() {

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

	for(int i = 1; i <= m; i++) e[i].x = in(), e[i].y = in(), e[i].z = in(), e[i].id = i;

	std::sort(e + 1, e + m + 1);

	int l = 0, r = 1e9;

	int ans = 0;

	while(l <= r) {

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

		if(ok(mid)) ans = mid, r = mid - 1;

		else l = mid + 1;

	}

	ok(ans);

	int tot = 0;

	for(int i = 1; i <= m; i++) if(vis[i]) tot++;

	printf("%d %d\n", ans, tot);

	for(int i = 1; i <= m; i++) if(vis[i]) printf("%d ", i);

	return 0;

}

巴特西

CF1100E Andrew and Taxi 二分答案+拓扑排序

\(\color{#0066ff}{ 题目描述 }\)

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

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

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

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

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

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

根据题目，显然要二分答案

考虑二分答案之后怎么做

对于比mid大的边，我们肯定是不能改变方向的

于是直接加入图中

然后只需看看有没有环就行了，因为比mid小的边我们可以任意更改

可以用拓扑排序做

因为它只让最大值最小，并没有说改变边的数量最小，所以小的边随便改

现在考虑输出方案

我们在拓扑排序的时候记一下每个点的拓扑序

考虑一条边x到y，如果x的拓扑序大于y，显然可能成环（不是一定成环）

但是如果x的拓扑序小于y，一定不会成环

题目有不限制改边数量，我们就将其反向即可

最新文章

热门文章