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

题意：一张无向图中有 n 个点，P 条边，每条边都有一个权值，且每条边只能用一次，要求找出 sum 条从 1 到 n 的路径，使这 sum 条路径所经过的边中，权值的最大值最小。(不是路径长度和，是路径中相邻两点的距离)

思路：二分路径最长的一段，根据二分值构图。
构图方法：
如果两点路径长度小于x，则两点之间连接一条边，权值为1（如果已经连接了，权值加1）。
最大流既是从1到n不重复的路径条数，判断是否大于规定的t条即可。

重边要当两条边来用。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int inf=0x3f3f3f3f;
int head[510],num[510],d[510],pre[510],cur[510],q[510];
int n,s,t,nv,cnt,sum;
int maxint=inf;
struct node {
    int u,v,cap;
    int next;
} edge[4000010];

struct node1 {
    int u,v;
    int w;
} p[4000010];

void add(int u,int v,int cap)
{
    edge[cnt].v=v;
    edge[cnt].cap=cap;
    edge[cnt].next=head[u];
    head[u]=cnt++;

    edge[cnt].v=u;
    edge[cnt].cap=cap;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}

void bfs()
{
    memset(num,0,sizeof(num));
    memset(d,-1,sizeof(d));
    int f1=0,f2=0,i;
    q[f1++]=t;
    num[0]=1;
    d[t]++;
    while(f1>=f2) {
        int u=q[f2++];
        for(i=head[u]; i!=-1; i=edge[i].next) {
            int v=edge[i].v;
            if(d[v]!=-1) continue;
            d[v]=d[u]+1;
            num[d[v]]++;
            q[f1++]=v;
        }
    }
}

int isap()
{
    memcpy(cur,head,sizeof(cur));
    int flow=0, u=pre[s]=s, i;
    bfs();
    while(d[s]<nv) {
        if(u==t) {
            int f=maxint, pos;
            for(i=s; i!=t; i=edge[cur[i]].v) {
                if(f>edge[cur[i]].cap) {
                    f=edge[cur[i]].cap;
                    pos=i;
                }
            }
            for(i=s; i!=t; i=edge[cur[i]].v) {
                edge[cur[i]].cap-=f;
                edge[cur[i]^1].cap+=f;
            }
            flow+=f;
            if(flow>=sum)
                return flow;
            u=pos;
        }
        for(i=cur[u]; i!=-1; i=edge[i].next) {
            if(d[edge[i].v]+1==d[u]&&edge[i].cap) {
                break;
            }
        }
        if(i!=-1) {
            cur[u]=i;
            pre[edge[i].v]=u;
            u=edge[i].v;
        } else {
            if(--num[d[u]]==0) break;
            int mind=nv;
            for(i=head[u]; i!=-1; i=edge[i].next) {
                if(mind>d[edge[i].v]&&edge[i].cap) {
                    mind=d[edge[i].v];
                    cur[u]=i;
                }
            }
            d[u]=mind+1;
            num[d[u]]++;
            u=pre[u];
        }
    }
    return flow;
}

int main()
{
    int n, P, i, j;
    while(~scanf("%d %d %d",&n,&P,&sum)) {
        for(i=0;i<P;i++)
            scanf("%d %d %d",&p[i].u,&p[i].v,&p[i].w);
        int low=1,mid,high=1000001;
        int ans=-1, x;
        while(low<=high) {
            mid=(high+low)/2;
            s=1;
            t=n;
            nv=t+1;
            cnt=0;
            memset(head,-1,sizeof(head));
            for(i=0; i<P; i++) {
                if(p[i].w<=mid) {
                    add(p[i].u,p[i].v,1);
                }
            }
            x=isap();
            if(x>=sum) {
                ans=mid;
                high=mid-1;
            }
            else
                low=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}