POJ2391 (Ombrophobic Bovines)[网络流，二分，Floyd]

发表于 | 更新于 | | 阅读次数：

题目链接：http://poj.org/problem?id=2391

这题一开始想成了费用流，不过应该有些细节没考虑到，一直WA。
这题的做法是二分网络流，先用Floyd预处理出任意两个结点的距离，二分这个距离，在跑最大流时只走小于这个距离的边，找到最大流能等于奶牛数的最小距离即可。
有个细节需要注意，结点是需要拆成入点和出点的，超级源向入点连边，出点向超级汇点连边，出点向入点连距离为最小距离容量为INF的边，这样能防止一些比较奇怪的问题，比如最小距离叠加到新的最小距离上了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const ll INF=1000000000LL*1500;

const int inf=0x7fffffff,N=409,M=400009;
int d[N],head[M],e[M],next[M],ver[M];
int et[M];
int s,t,m,n,tot=1;
ll dis[209][209];
ll ed[M];
int cnt=0;
void add(int u,int v,int w,ll dd=0) {
    ver[++tot]=v;ed[tot]=dd;e[tot]=w;next[tot]=head[u];head[u]=tot;
    ver[++tot]=u;ed[tot]=dd;e[tot]=0;next[tot]=head[v];head[v]=tot;
}
bool bfs(ll mid) {
    queue<int> q;
    memset(d,0,sizeof(d));
    q.push(s); d[s]=1;
    while(!q.empty()) {
        int x=q.front(); q.pop();
        for(int i=head[x];i;i=next[i]) {
            if(e[i]&&!d[ver[i]]&&ed[i]<=mid) {
                q.push(ver[i]);
                d[ver[i]]=d[x]+1;
                if(ver[i]==t) return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int f,ll mid) {
    int rest=f;
    if(x==t) return f;
    for(int i=head[x];i&&rest;i=next[i]) {
        if(e[i]&&d[ver[i]]==d[x]+1&&ed[i]<=mid) {
            int now=dinic(ver[i],min(e[i],rest),mid);
            if(!now) d[ver[i]]=0;
            e[i]-=now;
            e[i^1]+=now;
            rest-=now;
        }
    }
    return f-rest;
}
void floyd() {
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
bool check(ll mid) {
    int tmp=0;
    int maxflow=0;
    memcpy(e,et,sizeof(et));
    while(bfs(mid))
        while(tmp=dinic(s,inf,mid)) maxflow+=tmp;
    return maxflow==cnt;
}
int main() {
    int cm;
    int cow,shel;
    int u,v;
    ll w;
    scanf("%d%d",&n,&cm);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        if(i!=j) dis[i][j]=INF;
        else dis[i][j]=0;
    s=0;
    t=n*2+1;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&cow,&shel);
        cnt+=cow;
        if(cow>0) {
            add(s,i,cow);
        }
        if(shel>0) {
            add(i+n,t,shel);
        }
    }
    for(int i=0;i<cm;i++) {
        scanf("%d%d%I64d",&u,&v,&w);
        dis[u][v]=dis[v][u]=min(dis[u][v],w);
    }

    floyd();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(dis[i][j]!=INF) {
            add(i,j+n,inf,dis[i][j]);
        }

    memcpy(et,e,sizeof(e));
    ll l=0,r=1000000000LL*1500,mid;
    while(l<r) {
        mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    if(check(l)) printf("%I64d",l);
    else printf("-1");
    return 0;
}