loj#115. 无源汇有上下界可行流

$\color{#0066ff}{ 题目描述 }$

这是一道模板题。

$n$ 个点，$m$ 条边，每条边 $e$ 有一个流量下界 $\text{lower}(e)$ 和流量上界 $\text{upper}(e)$，求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。

$\color{#0066ff}{ 输入格式 } $

第一行两个正整数 $n$、$m$。

之后的 $m$ 行，每行四个整数 $s$、$t$、$\text{lower}$、$\text{upper}$。

$\color{#0066ff}{输出格式}$

如果无解，输出一行 NO。

否则第一行输出 YES，之后 $m$ 行每行一个整数，表示每条边的流量。

$\color{#0066ff}{输入样例}$

$\color{#0066ff}{输出样例}$

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

1≤n≤200,1≤m≤10200

$\color{#0066ff}{ 题解 }$

无源汇有上下界可行流判断

无源汇是没有s和t

有上下界是指每个边的流量要在一个$[l,r]$内

可行流，指的是每条边都要有一个合法流，使得对于任意一个点入流=出流

这个要怎么求？

对于一条边$x\to y$，上下界为[l,r]

显然如果成立，这条边最少流l

把一条边拆成两条，一条容量为r-l，一条容量为l，那么容量为l的那条边是一定要流满的

我们建立一个超级源s和超级汇t

对于$x\to y$

从x到y连容量为r-l的边，向y连容量为l的边， x向t连容量为l的边

即强制给yl的流，通过一些环（其它路径）流到x

最后只需判断s出去的边的所有容量和与最大流是否相等即可

当且仅当所有l的边都流满了才有解，对于那些r-l的边，随便流多少，一定在范围内的

最后实际上每条边的流量就是r-l的边的流量+l

#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 = 3e4 + 10;

struct node	{

	int to, dis, id;

	node *nxt, *rev;

	node(int to = 0, int dis = 0, int id = 0, node *nxt = NULL, node *rev = NULL)

		: to(to), dis(dis), id(id), nxt(nxt), rev(rev) {}

	void *operator new(size_t) {

		static node *S = NULL, *T = NULL;

		return (S == T) && (T = (S = new node[1024]) + 1024), S++;

	}

}*head[maxn], *cur[maxn];

int n, m, s, t, dep[maxn], ans[maxn], d[maxn];

void add(int from, int to, int c, int id) {

	head[from] = new node(to, c, id, head[from], NULL);

}

void link(int from, int to, int c, int id) {

	add(from, to, c, 0);

	add(to, from, 0, id);

	head[from]->rev = head[to];

	head[to]->rev = head[from];

}

bool bfs() {

	std::queue<int> q;

	for(int i = s; i <= t; i++) dep[i] = 0, cur[i] = head[i];

	dep[s] = 1;

	q.push(s);

	while(!q.empty()) {

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

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

			if(!dep[i->to] && i->dis)

				dep[i->to] = dep[tp] + 1, q.push(i->to);

	}

	return dep[t];

}

int dfs(int x, int change) {

	if(x == t || !change) return change;

	int flow = 0, ls;

	for(node *i = cur[x]; i; i = i->nxt) {

		cur[x] = i;

		if(dep[i->to] == dep[x] + 1 && (ls = dfs(i->to, std::min(change, i->dis)))) {

			flow += ls;

			change -= ls;

			i->dis -= ls;

			i->rev->dis += ls;

			if(!change) break;

		}

	}

	return flow;

}

int dinic() {

	int flow = 0;

	while(bfs()) flow += dfs(s, 0x7ffffff);

	return flow;

}

int main() {

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

	s = 0, t = n + 1;

	int x, y, l, r, tot = 0;

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

		x = in(), y = in(), l = in(), r = in();

		d[i] = l;

		link(x, y, r - l, i);

		link(s, y, l, 0);

		link(x, t, l, 0);

		tot += l;

	}

	if(tot == dinic()) {

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

			for(node *j = head[i]; j; j = j->nxt)

				if(j->id)

					ans[j->id] = d[j->id] + j->dis;

		printf("YES\n");

		for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);

	}

	else printf("NO");

	return 0;

}

巴特西

loj#115. 无源汇有上下界可行流

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

$\color{#0066ff}{ 输入格式 } $

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

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

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

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

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

无源汇有上下界可行流判断

无源汇是没有s和t

有上下界是指每个边的流量要在一个\([l,r]\)内

可行流，指的是每条边都要有一个合法流，使得对于任意一个点入流=出流

这个要怎么求？

对于一条边\(x\to y\)，上下界为[l,r]

显然如果成立，这条边最少流l

把一条边拆成两条，一条容量为r-l，一条容量为l，那么容量为l的那条边是一定要流满的

我们建立一个超级源s和超级汇t

对于\(x\to y\)

从x到y连容量为r-l的边，向y连容量为l的边， x向t连容量为l的边

即强制给yl的流，通过一些环（其它路径）流到x

最后只需判断s出去的边的所有容量和与最大流是否相等即可

当且仅当所有l的边都流满了才有解，对于那些r-l的边，随便流多少，一定在范围内的

最后实际上每条边的流量就是r-l的边的流量+l

最新文章

热门文章

巴特西

loj#115. 无源汇有上下界可行流

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

$\color{#0066ff}{ 输入格式 } $

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

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

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

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

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

无源汇有上下界可行流判断

无源汇是没有s和t

有上下界是指每个边的流量要在一个\([l,r]\)内

可行流，指的是每条边都要有一个合法流，使得对于任意一个点入流=出流

这个要怎么求？

对于一条边\(x\to y\)，上下界为[l,r]

显然如果成立，这条边最少流l

把一条边拆成两条，一条容量为r-l， 一条容量为l，那么容量为l的那条边是一定要流满的

我们建立一个超级源s和超级汇t

对于\(x\to y\)

从x到y连容量为r-l的边， 向y连容量为l的边， x向t连容量为l的边

即强制给yl的流，通过一些环（其它路径）流到x

最后只需判断s出去的边的所有容量和与最大流是否相等即可

当且仅当所有l的边都流满了才有解，对于那些r-l的边，随便流多少，一定在范围内的

最后实际上每条边的流量就是r-l的边的流量+l

最新文章

热门文章

把一条边拆成两条，一条容量为r-l，一条容量为l，那么容量为l的那条边是一定要流满的

从x到y连容量为r-l的边，向y连容量为l的边， x向t连容量为l的边