首页 > 代码库 > POJ 2391 Ombrophobic Bovines （二分 + floyd + 网络流）
POJ 2391 Ombrophobic Bovines （二分 + floyd + 网络流）
POJ 2391 Ombrophobic Bovines
链接：http://poj.org/problem?id=2391
题目：农场有F 块草地，1≤F≤200，奶牛们在草地上吃草。这些草地之间有P 条路相连，1≤P≤1500，这些路足够宽，再多的奶牛也能同时在路上行走。有些草地上有避雨点，奶牛们可以在此避雨。避雨点的容量是有限的，所以一个避雨点不可能容纳下所有的奶牛。草地与路相比很小，奶牛们通过时不需要花费时间。计算警报至少需要提前多少时间拉响，以保证所有的奶牛都能到达一个避雨点。
思路：先对草地做一次floyd得到任意两点之间的距离。然后将草地拆点，拆为有牛的草地和有避雨点的草地，两者的距离为0。之后便对时间进行二分。对于每一个mid，建立一个源点，向每一个有牛的草地连边，流量为草地奶牛数量。建立一个汇点，每一个避雨点向汇点连边，流量为容量。两点距离小于等于mid的点连边，流量为INF。之后跑网络最大流即可。
细节：这道题细节比较多，一：是两点之间可能有多条路径；二：最大距离超int了。还有一开始的时候我没有将拆开的两个点之间连边。
代码：
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define LINF (1LL<<60)
#define INF (1<<30)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-6
#define debug puts("===============")
#define pb push_back
//#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
typedef long long ll;
typedef unsigned long long ULL;
const int maxn = 610;
const int maxm = 2000000;
int land[210][2], F, P, sumst, sumed;
ll mp[210][210], mx;
int st, ed, n;
int is[210][2];
void get() {
scanf("%d%d", &F, &P);
n = 1;
for (int i = 1; i <= F; i++) {
scanf("%d%d", land[i], land[i] + 1);
sumst += land[i][0];
sumed += land[i][1];
if (land[i][0]) is[i][0] = n++;
if (land[i][1]) is[i][1] = n++;
for (int j = 1; j <= F; j++) mp[i][j] = LINF;
mp[i][i] = 0;
}
int u, v, c;
for (int i = 0; i < P; i++) {
scanf("%d%d%d", &u, &v, &c);
if (mp[u][v] > c) mp[u][v] = mp[v][u] = c; //图中两点可能有多条边
}
}
void floyd(int n, ll mp[][210]) {
mx = 0;
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) if (mp[i][k] != LINF) {
for (int j = 1; j <= n; j++) {
mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
if (mp[i][j] != LINF) mx = max(mx, mp[i][j]);
}
}
}
}
struct node {
int v; // vertex
int cap; // capacity
int flow; // current flow in this arc
int nxt;
} e[maxm * 2];
int g[maxn], cnt;
void add(int u, int v, int c) {
e[++cnt].v = v;
e[cnt].cap = c;
e[cnt].flow = 0;
e[cnt].nxt = g[u];
g[u] = cnt;
e[++cnt].v = u;
e[cnt].cap = 0;
e[cnt].flow = 0;
e[cnt].nxt = g[v];
g[v] = cnt;
}
void init(ll mid) {
mem(g, 0);
cnt = 1;
st = 0;
ed = n++;
for (int i = 1; i <= F; i++) if (land[i][0]) add(st, is[i][0], land[i][0]);
for (int i = 1; i <= F; i++) if (land[i][1]) add(is[i][1], ed, land[i][1]);
for (int i = 1; i <= F; i++) {
for (int j = i; j <= F; j++) if (mp[i][j] <= mid) { //j从i开始，因为有草地既有牛，也有避雨点
if (land[i][0] && land[j][1]) add(is[i][0], is[j][1], INF);
if (land[j][0] && land[i][1]) add(is[j][0], is[i][1], INF);
}
}
}
int dist[maxn], numbs[maxn], q[maxn];
void rev_bfs() {
int font = 0, rear = 1;
for (int i = 0; i <= n; i++) { //n为总点数
dist[i] = maxn;
numbs[i] = 0;
}
q[font] = ed;
dist[ed] = 0;
numbs[0] = 1;
while(font != rear) {
int u = q[font++];
for (int i = g[u]; i; i = e[i].nxt) {
if (e[i ^ 1].cap == 0 || dist[e[i].v] < maxn) continue;
dist[e[i].v] = dist[u] + 1;
++numbs[dist[e[i].v]];
q[rear++] = e[i].v;
}
}
}
int maxflow() {
rev_bfs();
int u, totalflow = 0;
int curg[maxn], revpath[maxn];
for(int i = 0; i <= n; ++i) curg[i] = g[i];
u = st;
while(dist[st] < n) {
if(u == ed) { // find an augmenting path
int augflow = INF;
for(int i = st; i != ed; i = e[curg[i]].v)
augflow = min(augflow, e[curg[i]].cap);
for(int i = st; i != ed; i = e[curg[i]].v) {
e[curg[i]].cap -= augflow;
e[curg[i] ^ 1].cap += augflow;
e[curg[i]].flow += augflow;
e[curg[i] ^ 1].flow -= augflow;
}
totalflow += augflow;
u = st;
}
int i;
for(i = curg[u]; i; i = e[i].nxt)
if(e[i].cap > 0 && dist[u] == dist[e[i].v] + 1) break;
if(i) { // find an admissible arc, then Advance
curg[u] = i;
revpath[e[i].v] = i ^ 1;
u = e[i].v;
} else { // no admissible arc, then relabel this vertex
if(0 == (--numbs[dist[u]])) break; // GAP cut, Important!
curg[u] = g[u];
int mindist = n;
for(int j = g[u]; j; j = e[j].nxt)
if(e[j].cap > 0) mindist = min(mindist, dist[e[j].v]);
dist[u] = mindist + 1;
++numbs[dist[u]];
if(u != st)
u = e[revpath[u]].v; // Backtrack
}
}
return totalflow;
}
int main () {
get();
floyd(F, mp);
if (sumst > sumed) {
puts("-1");
return 0;
}
init(mx);
if (maxflow() < sumst) {
puts("-1");
return 0;
}
ll l = 0, r = mx, mid;
while(l < r) {
mid = (l + r) >> 1;
init(mid);
if (maxflow() >= sumst) r = mid;
else l = mid + 1;
}
printf("%lld\n", r);
return 0;
}
POJ 2391 Ombrophobic Bovines （二分 + floyd + 网络流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。