POJ 2391--Ombrophobic Bovines【拆点 && 二分 && 最大流dinic && 经典】

Description

Input

Output

Sample Input

3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120

Sample Output

110

Hint

题意：

有n个田地，给出每个田地上初始的牛的数量和每个田地可以容纳的牛的数量。

m条双向的路径，每条路径上可以同时通过的牛没有限制。

问牛要怎么走，能在最短时间内使得每块田地都能容纳的下，输出最短时间或-1。

思路：

先floyd求出任意两点之间的最短距离，然后二分答案，判断是否可以在时间不超过mid的情况下完成移动：

建图：

每个点拆成两个点 x 和 x‘，源点向 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 <queue>
#define maxn 600
#define maxm 1000000
#define INF 1000000000 + 1000
#define INF1 1e16
using namespace std;

struct node {
    int u, v, cap, flow, next;
};

node edge[maxm];
long long map[maxn][maxn];
int head[maxn], cur[maxn], cnt;
int dist[maxn], vis[maxn];
int all[maxn], can[maxn];
int F, P, sum;

void init(){
    cnt = 0;
    memset(head, -1, sizeof(head));
}

void add(int u, int v, int w){
    edge[cnt] = {u, v, w, 0, head[u]};
    head[u] = cnt++;
    edge[cnt] = {v, u, 0, 0, head[v]};
    head[v] = cnt++;

}
void floy(){
    int i, j, k;
    for(k = 1; k <= F; ++k)
        for(i = 1; i <= F; ++i){
            if(map[i][k] != INF1)
                for(j = 1; j <= F; ++j)
                    map[i][j] = min(map[i][k] + map[k][j], map[i][j]);
        }
}


void getmap(long long min_max){
    for(int i = 1; i <= F; ++i){
        add(0, i, all[i]); //0 为源点
        add(i + F, 2 * F + 1, can[i]); //2 * F + 1 为汇点
    }
    for(int i = 1; i <= F; ++i)
    for(int j = 1; j <= F; ++j)
        if(map[i][j] <= min_max)
        add(i, j + F, INF);
}

bool BFS(int st, int ed){
    queue<int>q;
    memset(vis, 0, sizeof(vis));
    memset(dist, -1, sizeof(dist));
    q.push(st);
    vis[st] = 1;
    dist[st] = 0;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = head[u]; i != -1; i = edge[i].next){
            node E = edge[i];
            if(!vis[E.v] && E.cap > E.flow){
                vis[E.v] = 1;
                dist[E.v] = dist[u] + 1;
                if(E.v == ed) return true;
                q.push(E.v);
            }
        }
    }
    return false;
}

int DFS(int x, int ed, int a){
    if(a == 0 || x == ed)
        return a;
    int flow = 0, f;
    for(int &i = cur[x]; i != -1; i =edge[i].next){
        node &E = edge[i];
        if(dist[E.v] == dist[x] + 1 && (f = DFS(E.v, ed, min(a, E.cap - E.flow))) > 0){
            E.flow += f;
            edge[i ^ 1].flow -= f;
            flow += f;
            a -= f;
            if(a == 0) break;
        }
    }
    return flow;
}

int maxflow (int st, int ed){
    int flowsum  = 0;
    while(BFS(st, ed)){
        memcpy(cur, head, sizeof(head));
        flowsum += DFS(st, ed, INF);
    }
    return flowsum;
}

int main (){
    while(scanf("%d%d", &F, &P) != EOF){
        sum = 0;
        for(int i = 1; i <= F; ++i){
            scanf("%d%d", &all[i], &can[i]);
            sum += all[i];
        }
        for(int i = 1; i <= F; ++i)
        for(int j = 1; j <= F; ++j){
            if(i == j)
                map[i][j] = 0;
            else
                map[i][j] = map[j][i] = INF1;
        }
        int u ,v, w;
        for(int i = 1; i <= P; ++i){
            scanf("%d%d%d", &u, &v, &w);
            if(map[u][v] > w)
                map[u][v] = map[v][u] = w;
        }
        floy();
        long long r = INF1;
        long long l = 0;
        long long mid, ans;
        long long num = -1;
        while(r > l){
            mid  = (l + r) / 2;
            ans = 0;
            init();
            getmap(mid);
            ans = maxflow(0, 2 * F + 1);
            if(ans >= sum) {
                r = mid;
                num = mid;
            }
            else l = mid + 1;
        }
        printf("%lld\n", num);
    }
    return 0;
}

POJ 2391--Ombrophobic Bovines【拆点 && 二分 && 最大流dinic && 经典】

原文：http://blog.csdn.net/hpuhjh/article/details/47320181