「POI2010」Bridges

解题思路

首先二分答案，然后在所有边权小于二分值的边和所有点组成的图中判欧拉回路。

由于可能出现混合图，所以要用到网络流。

把所有无向边钦定一个方向，那么原图就是一个有向图。

那么存在欧拉回路的充要条件就所有点的入度等于出度且图联通。

我们考虑把点 \(x\) 的入度与出度之差记作 \(\Delta x\)。

那么对于所有的定向后的无向边 \((u,v)\)，连一条从 \(u\rightarrow v\) 的容量为 \(1\) 的边。

表示将该条边反向可以使 \(\Delta u += 2,\Delta v -= 2\)。

然后考虑对于所有度数差小于 \(0\) 的点 \(x\)，连一条 \(s \rightarrow x\) 的容量为 \(\frac{|\Delta x|}{2}\) 的边。

表示 \(x\) 需要操作这么多次，使得 \(\Delta x\) 达到 \(0\)。小于零的情况同理。

最后判断是否满流即可。

细节注意事项

细节有点多，要有耐心

参考代码

#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 _ = 1010;

const int __ = 5010 * 2 + 1010 * 2;

const int INF = 2147483647;

int tot = 1, head[_], nxt[__], ver[__], cap[__];

inline void Add_edge(int u, int v, int d)

{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v, cap[tot] = d; }

inline void link(int u, int v, int d) { Add_edge(u, v, d), Add_edge(v, u, 0); }

int n, m, s, t, liu, dgr[_], dep[_];

struct node{ int a, b, c, d; }g[__];

inline int bfs() {

	static queue < int > Q;

	memset(dep, 0, sizeof dep);

	dep[s] = 1, Q.push(s);

	while (!Q.empty()) {

		int u = Q.front(); Q.pop();

		for (rg int i = head[u]; i; i = nxt[i]) {

			int v = ver[i];

			if (dep[v] == 0 && cap[i] > 0)

				dep[v] = dep[u] + 1, Q.push(v);

		}

	}

	return dep[t] > 0;

}

inline int dfs(int u, int flow) {

	if (u == t) return flow;

	for (rg int i = head[u]; i; i = nxt[i]) {

		int v = ver[i];

		if (dep[v] == dep[u] + 1 && cap[i] > 0) {

			int res = dfs(v, min(flow, cap[i]));

			if (res) { cap[i] -= res, cap[i ^ 1] += res; return res; }

		}

	}

	return 0;

}

inline int Dinic() {

	int res = 0;

	while (bfs()) while (int d = dfs(s, INF)) res += d;

	return res;

}

inline bool check(int mid) {

	s = 0, t = n + 1;

	tot = 1, memset(head, 0, sizeof head);

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

		if (g[i].c > mid) return 0;

		if (g[i].d <= mid) link(g[i].a, g[i].b, 1);

	}

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

		if (dgr[i] < 0) link(s, i, -dgr[i] / 2);

		if (dgr[i] > 0) link(i, t, dgr[i] / 2);

	}

	return Dinic() == liu / 2;

}

int main() {

#ifndef ONLINE_JUDGE

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

#endif

	read(n), read(m);

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

		read(g[i].a), read(g[i].b), read(g[i].c), read(g[i].d);

		if (g[i].c > g[i].d)

			swap(g[i].a, g[i].b), swap(g[i].c, g[i].d);

		--dgr[g[i].a], ++dgr[g[i].b];

	}

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

		if (dgr[i] % 2 != 0) return puts("NIE"), 0;

		liu += abs(dgr[i]) / 2;

	}

	int l = 1, r = 1000;

	while (l < r) {

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

		if (check(mid)) r = mid;

		else l = mid + 1;

	}

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

	return 0;

}

完结撒花 \(qwq\)

巴特西

「POI2010」Bridges

解题思路

细节注意事项

参考代码

最新文章

热门文章