本文主要是介绍POJ 2391 Ombrophobic Bovines(二分+floyd+拆点+Dinic网络流)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有n个田地，给出每个田地上初始的牛的数量和每个田地可以容纳的牛的数量。m条双向的路径，每条路径上可以同时通过的牛没有限制。
问牛要怎么走，能在最短时间内使得每块田地都能容纳的下，输出最短时间或-1。
分析：先floyd求出任意两点之间的最短距离，然后二分答案，判断是否可以在时间不超过mid的情况下完成移动：
建图：
每个点拆成两个点x（i）和x'(i+n)，源点向x连边，权值为初始的牛的数量；
x'向汇点连边，权值为可以容纳的牛的数量；
x向x'连边，权值为INF。
然后枚举任意两点i和j，如果i和j之间的最短距离dist[i][j]<=mid，则建边i->j'，权值为INF。
此时计算最大流，就是在限定mid时间内可以移动的最多的牛的数量，如果大于等于牛的总数则说明可行，否则不可行。继续二分。
参考：点击打开链接
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#define T (n << 1 | 1)
using namespace std;
const long long INF = 1e16;
struct Edge{ //建边 int from, to, cap; Edge() {} Edge(int a, int b, int c) : from(a), to(b), cap(c) {}
}; int n, m;
int sum;
long long arr[405][405]; //arr[i][j]表示i到j的最短路，也就是最短时间
int cow[405]; //cow[i] ,i节点的牛的数量
int cap[405]; //cap[i]，i节点的棚子所能容纳的牛的数量
vector<Edge> edges; //边 表
vector<int> G[405]; //邻接表，G[i][j]表示结点i的第j条边在e数组的序号 void floyd() { //floyd算法求最短 for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
} void addEdge(int from, int to, int cap) { //建边 edges.push_back(Edge(from, to, cap)); edges.push_back(Edge(to, from, 0)); int siz = edges.size(); G[from].push_back(siz - 2); G[to].push_back(siz - 1);
} int cur[405]; //cur[i]表示当前正访问i结点的第cur[i]条弧
int layer[405]; //layer[i]表示 i所在的层次 //----------------------------------------------------------------Dinic开始---------------
bool build() { queue<int> q; //保存节点编号 memset(layer, -1, sizeof(layer)); q.push(0); layer[0] = 0; while (!q.empty()) { int current = q.front(); q.pop(); for (int i = 0; i < G[current].size(); i++) { Edge e = edges[G[current][i]]; if (layer[e.to] == -1 && e.cap > 0) { layer[e.to] = layer[current] + 1; q.push(e.to); } } } return layer[T] != -1;
} int find(int x, int curFlow) { if (x == T || !curFlow) return curFlow; int flow = 0, f; for (int &i = cur[x]; i < G[x].size(); i++) { Edge &e = edges[G[x][i]]; if (layer[e.to] == layer[x] + 1 && (f = find(e.to, min(curFlow, e.cap)))) { e.cap -= f; edges[G[x][i] ^ 1].cap += f; flow += f; curFlow -= f; if (!curFlow) break; } } return flow;
} int dinic() { int ans = 0; while (build()) { memset(cur, 0, sizeof(cur)); ans += find(0, 0x3f3f3f3f); } return ans;
}
//--------------------------------------------Dinic结束--------------------
void buildGraph(long long x) { //建图操作，详见分析 for (int i = 0; i <= T; i++) G[i].clear(); edges.clear(); for (int i = 1; i <= n; i++) { addEdge(0, i, cow[i]); addEdge(i + n, T, cap[i]); addEdge(i, i + n, 0x3f3f3f3f); } for (int i = 1; i <= n; i++) { //枚举任意两点i。j for (int j = i + 1; j <= n; j++) { if (arr[i][j] <= x) { addEdge(i, j + n, 0x3f3f3f3f); addEdge(j, i + n, 0x3f3f3f3f); } } }
} long long solve() { //二分枚举时间 long long ans = -1; long long l = 0, r = INF - 1; while (l <= r) { long long mid = l + r >> 1; buildGraph(mid); if (dinic() >= sum) { ans = mid; r = mid - 1; } else l = mid + 1; } return ans;
} int main() { while (~scanf("%d %d", &n, &m)) { sum = 0; for (int i = 1; i <= n; i++) { scanf("%d %d", &cow[i], &cap[i]); sum += cow[i]; } int a, b, c; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) arr[i][j] = INF; for (int i = 0; i < m; i++) { scanf("%d %d %d", &a, &b, &c); if (c < arr[a][b]) arr[a][b] = arr[b][a] = c; } floyd(); long long ans = solve(); printf("%lld\n", ans); } return 0;
}
这篇关于POJ 2391 Ombrophobic Bovines(二分+floyd+拆点+Dinic网络流)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
