本文主要是介绍【uva 563】【构图】【最大流】【拆点】【n*m网格上l个点到边界线路不重合问题】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题意】n*m网格上l个点到边界线路不重合问题
【思路】拆点，每个网格点拆为x,x'
有一个源点s（0）,汇点t(2*n*m+1)
主要是建图的思路：
1.x->x'(容量为1)，表示有一次机会过这个点
2.x'->上下左右四个入点，（容量为1），表示有一次机会走这个点
3.s->银行入点，容量inf(其实大于1就行了)
4.边界点->t,容量inf()
【代码】要写熟悉的代码哦
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const long long maxn = 1e5 + 5;
const long long N = 500100;
const long long M = 300010;
const long long OF = 2500;
const long long FIN = 5001;
long long dx[4] = { 0,0,1,-1 };
long long dy[4] = { 1,-1,0,0 };
long long n, m;
long long st, ed;long long head[N], ver[N], edge[M], nxt[M], d[M];
long long tot, maxflow;void add(long long x, long long y, long long z) {ver[++tot] = y; edge[tot] = z; nxt[tot] = head[x]; head[x] = tot;ver[++tot] = x; edge[tot] = 0; nxt[tot] = head[y]; head[y] = tot;
}long long bfs() {memset(d, 0, sizeof(d));queue<long long>q;q.push(st);d[st] = 1;while (q.size()) {long long x = q.front(); q.pop();for (long long i = head[x]; i; i = nxt[i]) {if (edge[i] && !d[ver[i]]) {q.push(ver[i]);d[ver[i]] = d[x] + 1;if (ver[i] == ed)return 1;}}}return 0;
}long long dinic(long long x, long long flow) {if (x == ed)return flow;long long rest = flow, k;for (long long i = head[x]; i&&rest; i = nxt[i]) {if (edge[i] && d[ver[i]] == d[x] + 1) {k = dinic(ver[i], min(rest, edge[i]));if (!k)d[ver[i]] = 0;edge[i] -= k;edge[i ^ 1] += k;rest -= k;}}return flow - rest;
}int main() {long long T;scanf("%lld", &T);while (T--) {tot = 1;long long a, b, s;scanf("%lld%lld%lld", &s, &a, &b);st = 0;ed = FIN;memset(head, 0, sizeof(head));for (long long i = 1; i <= s; i++) {for (long long j = 1; j <= a; j++) {add((i - 1)*a + j, (i - 1)*a + j + OF, 1);//x与x'之间连边权为1的点//出点向四个方向连边for (long long k = 0; k < 4; k++) {long long x = i + dx[k];long long y = j + dy[k];if (x<1 || x>s || y<1 || y>a)continue;add((i - 1)*a + j + OF, (x - 1)*a + y, 1);}if (i == 1 || i == s || j == 1 || j == a)//边界建边add((i - 1)*a + j + OF, FIN, inf);}}for (long long i = 1; i <= b; i++) {long long x, y;scanf("%lld%lld", &x, &y);add(0, (x - 1)*a + y, inf);}long long flow = 0;maxflow = 0;while (bfs()) {while (flow = dinic(st, inf))maxflow += flow;}printf("%s", maxflow == b ? "possible\n" : "not possible\n");}}/*2
6 6 10
4 1
3 2
4 2
5 2
3 4
4 4
5 4
3 6
4 6
5 6
5 5 5
3 2
2 3
3 3
4 3
3 4*/
这篇关于【uva 563】【构图】【最大流】【拆点】【n*m网格上l个点到边界线路不重合问题】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
