2095: [Poi2010]Bridges

二分答案，混合图欧拉路判定

一开始想了一个上下界网络流模型，然后发现不用上下界网络流也可以

对于无向边，强制从\(u \rightarrow v\)，计算每个点入度出度

两者差必须是偶数，令\(x = \frac{ind_i - outd_i}{2}\)

每条无向边v向u连容量为1的边

对于\(x>0\)， s向i连容量x的边；

\(x<0\)， i向t连容量-x的边。

这样一条原无向边满流就是与强制方向相反

有解当且仅当 s出边满流

本题l不能初始化0，貌似有什么诡异的特殊数据...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <set>

#include <map>

using namespace std;

typedef long long ll;

#define fir first

#define sec second

const int N = 2005, M = 1e4+5, inf = 1e9+5;

inline int read() {

    char c=getchar(); int x=0,f=1;

    while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}

    return x*f;

}

int n, m, s, t;

struct meow {int u, v, c, d;} a[M];

struct edge {int v, ne, c, f;} e[M];

int cnt = 1, h[N];

inline void ins(int u, int v, int c) { //printf("ins %d --> %d  %d\n", u, v, c);

	e[++cnt] = (edge) {v, h[u], c, 0}; h[u] = cnt;

	e[++cnt] = (edge) {u, h[v], 0, 0}; h[v] = cnt;

}

int d[N], q[N], head, tail, vis[N];

bool bfs() {

	memset(vis, 0, sizeof(vis));

	head = tail = 1;

	d[s] = 0; q[tail++] = s; vis[s] = 1;

	while(head != tail) {

		int u = q[head++];

		for(int i=h[u]; i; i=e[i].ne)

			if(e[i].c > e[i].f && !vis[e[i].v]) {

				int v = e[i].v;

				vis[v] = 1;

				d[v] = d[u]+1;

				q[tail++] = v;

				if(v == t) return true;

			}

	}

	return false;

}

int cur[N];

int dfs(int u, int a) {

	if(u == t || a == 0) return a;

	int flow = 0, f;

	for(int &i=cur[u]; i; i=e[i].ne) {

		int v = e[i].v;

		if(d[v] == d[u]+1 && (f = dfs(v, min(a, e[i].c - e[i].f))) > 0) {

			flow += f;

			e[i].f += f;

			e[i^1].f -= f;

			a -= f;

			if(a == 0) break;

		}

	}

	if(a) d[u] = -1;

	return flow;

}

int dinic() {

	int flow = 0;

	while(bfs()) {

		for(int i=s; i<=t; i++) cur[i] = h[i];

		flow += dfs(s, inf);

	}

	return flow;

}

int ind[N], outd[N];

bool check(int mid) { //printf("check %d\n", mid);

	cnt = 1; memset(h, 0, sizeof(h));

	s = 0; t = n+1;

	memset(ind, 0, sizeof(ind));

	memset(outd, 0, sizeof(outd));

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

		int u = a[i].u, v = a[i].v;

		if(a[i].c <= mid && a[i].d <= mid) {

			outd[u]++, ind[v]++;

			ins(v, u, 1);

		} else if(a[i].c <= mid) outd[u]++, ind[v]++;

		else if(a[i].d <= mid) outd[v]++, ind[u]++;

	}

	int sum = 0;

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

		int x = abs(ind[i] - outd[i]); //printf("x %d  %d\n", i, x);

		if(x & 1) return false;

		x >>= 1;

		if(ind[i] > outd[i]) ins(s, i, x), sum += x;

		else if(ind[i] < outd[i]) ins(i, t, x);

	}

	return dinic() == sum;

}

int main() {

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

	n = read(); m = read();

	int l = inf, r = 0, ans = -1;

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

		a[i].u = read(), a[i].v = read(), a[i].c = read(), a[i].d = read();

		l = min(l, min(a[i].c, a[i].d));

		r = max(r, max(a[i].c, a[i].d));

	}

	//printf("%d\n", check(4)); return 0;

	while(l <= r) {

		int mid = (l+r) >> 1; //printf("lrmid %d %d %d\n", l, r, mid);

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

		else l = mid+1;

	}

	if(ans == -1) puts("NIE");

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

}

巴特西

bzoj 2095: [Poi2010]Bridges [混合图欧拉回路]

2095: [Poi2010]Bridges

最新文章

热门文章