POJ 2455--Secret Milking Machine【二分枚举 && 最大流 && 经典】

Description

Input

Output

Sample Input

7 9 2
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3

Sample Output

5

Hint

题意：

题意：给你一个N个点（编号从1到N）和M条边的无向图以及每条边的权值。要求从1到N至少要有T条边不重复的路径，让你在满足这个前提下求出所有路径（当然是选出的那些边不重复的路径，不算没有选上的）上的最大边权值的 最小值。

解析：一看到最大值的最小化问题就想到用二分做，题目保证从1 到 N有 T 条无相同道路的路径，即每条边只能用一次，每个点可以多次经过。边不重复的路径数目可以用最大流求解。二分枚举最大边权值mid ，再枚举所有的边，若边的权值 <= mid, 加进网络流中，且容量为1，，然后跑最大流，看看最大流是不是>= T,符合的话取更新最大权值的最小值，取最小值。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 220
#define maxm 2000000
#define INF 0x3f3f3f3f
using namespace std;
int N, M, T;

struct NODE{
    int u, v, w, next;
};

NODE map[maxm];
int head1[maxn], cnt1;

void initmap(){
    cnt1 = 0;
    memset(head1, -1, sizeof(head1));
}

void addmap(int u ,int  v, int w){
    map[cnt1].u = u;
    map[cnt1].v = v;
    map[cnt1].w = w;
    map[cnt1].next = head1[u];
    head1[u] = cnt1++;
}
int maxs = 0;
void input(){
    initmap();
    while(M--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        maxs = max(maxs, c);
        addmap(a, b, c);
        addmap(b, a, c);
    }
}

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

node edge[maxm];
int head[maxn], cnt, cur[maxn];
int vis[maxn], dist[maxn];

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

void addedge(int u, int v, int w){
    edge[cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].cap = w;
    edge[cnt].flow = 0;
    edge[cnt].next = head[u];
    head[u] = cnt++;
    edge[cnt].u = v;
    edge[cnt].v = u;
    edge[cnt].cap = 0;
    edge[cnt].flow = 0;
    edge[cnt].next = head[v];
    head[v] = cnt++;
}

void getmap(int ans){
    for(int i = 0; i < cnt1; ++i)
        if(map[i].w <= ans)
        addedge(map[i].u, map[i].v, 1);
}

bool BFS(int st ,int ed){
    queue<int>q;
    memset(vis, 0 ,sizeof(vis));
    memset(dist, -1, sizeof(dist));
    vis[st] = 1;
    dist[st] = 0;
    q.push(st);
    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(x == ed || a == 0)
        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;
            a -= f;
            flow += 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%d", &N, &M, &T) != EOF){
        input();
        int l = 0, r = maxs, mid;
        int max_min = maxs;
        while(r > l){
            mid  = (l + r) / 2;
            initedge();
            getmap(mid);
            if(maxflow(1, N) >= T){
                max_min = min(max_min, mid);
                r = mid;
            }
            else
                l = mid + 1;
        }
        printf("%d\n", max_min);
    }
    return 0;
}

POJ 2455--Secret Milking Machine【二分枚举 && 最大流 && 经典】

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