POJ 2391 Ombrophobic Bovines【网络流建模汇总】拆点最大流

题意:一个无向图。点i处有Ai头牛,牛棚能够容纳Bi头牛,从i到j有个时间,求一个最短时间T,让所有的牛都能够进入牛棚



这个题呢,思路其实很简单:二分时间就能找到最小值,对于每个时间点T0,判断是不是可行就好

可行的意思:在给定的时间内,跑出来的最大流等于各个点的牛的数量之和

时间影响了什么?影响了从i点到j点能不能去。时间不够的话,就去不了

然后看看题目中的数据,n不超过200:所以用floyd算法得到任意两点之间的最短时间

这样建模就很清晰了:


拆点:

对于任意不同的两点i,j:如果time【i】【j】不超过当前二分的时间T0,说明第i个点的牛在时间内可以到第j个牛棚

所以连边(i1,j2,INF)容量为INF是说,第i个牛棚的所有牛都可以去(当然用Ai也可以)


必须有的边:

源点到所有的点:(s,i1,Ai),这个是牛的数量的限制

所有的点到汇点:(i2,t,Bi),这个是牛棚中的最大值的限制


然后,拆点之后,自己和自己必须连边:因为距离为0,无论时间多少都是可以去到的点

(i1,i2,INF)



其实,这个题的难点不在拆点和连边:那么在哪儿?

在如何确定二分的L,R中的R(也就是最大时间上限):是题目中的1e9这个值吗?

考虑一组非常特别特殊的数据:

10 9
1 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 1
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000

看到这种特别恶心的数据:我们知道最后的答案是
9000000000
因为从1到10只有一条路径,必须慢慢的走


那么,拓展看来,如果都是这种边,最大的时间可能是1000*1e9=1e12(注意,这个值已经超过int了,需要用long long来搞)

所以把值设为这个应该就是没有问题的(当然二分是比较快的,再设大几个数量级其实更保险,反正多算不了几次)

讨论了这些,注意好细节,应该可以上代码上模板1A了吧:


#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<stdio.h>
#include<cstring>
#include<string.h>
using namespace std;

#define LL long long
const int maxm=50000;
const int maxn=1050;
const int INF=0x3f3f3f3f;
const LL LLINF=1e16;
int s,t,tot;
int n,m;
int f[maxn];
int p[maxn];
int all;
LL L,R,ans,mid,dist[maxn][maxn];

struct Edge{
    int to,nxt,cap,flow;
}edge[maxm*10];
int tol,Head[maxm*10];

void init(){
    memset(Head,-1,sizeof(Head));
    tol=2;
}

void addedge(int u,int v,int w,int rw=0){
    edge[tol].to=v;
    edge[tol].cap=w;
    edge[tol].flow=0;
    edge[tol].nxt=Head[u];
    Head[u]=tol++;

    edge[tol].to=u;
    edge[tol].cap=rw;
    edge[tol].flow=0;
    edge[tol].nxt=Head[v];
    Head[v]=tol++;
}

int Q[maxn*10],dep[maxn*10],cur[maxn*10],sta[maxn*10];

bool bfs(int s,int t,int n){
    int Front=0,Tail=0;
    memset(dep,-1,sizeof(dep[0])*(n+1));
    dep[s]=0;
    Q[Tail++]=s;
    while(Front<Tail){
        int u=Q[Front++];
        for(int i=Head[u];i!=-1;i=edge[i].nxt){
            int v=edge[i].to;
            if (edge[i].cap>edge[i].flow&&dep[v]==-1){
                dep[v]=dep[u]+1;
                if (v==t) return true;
                Q[Tail++]=v;
            }
        }
    }
    return false;
}

int dinic(int s,int t,int n){
    int maxflow=0;
    while(bfs(s,t,n)){
        for(int i=0;i<n;i++) cur[i]=Head[i];
        int u=s,tail=0;
        while(cur[s]!=-1){
            if (u==t){
                int tp=INF;
                for(int i=tail-1;i>=0;i--)
                    tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
                maxflow+=tp;
                for(int i=tail-1;i>=0;i--){
                    edge[sta[i]].flow+=tp;
                    edge[sta[i]^1].flow-=tp;
                    if (edge[sta[i]].cap==edge[sta[i]].flow) tail=i;
                }
                u=edge[sta[tail]^1].to;
            }
            else if (cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to]){
                sta[tail++]=cur[u];
                u=edge[cur[u]].to;
            }
            else{
                while(u!=s&&cur[u]==-1) u=edge[sta[--tail]^1].to;
                cur[u]=edge[cur[u]].nxt;
            }
        }
    }
    return maxflow;
}

void add(LL x){
    init();
    for(int i=1;i<=n;i++){
        addedge(s,i,f[i]);
        addedge(i+n,t,p[i]);
        addedge(i,i+n,INF);
    }
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        if (dist[i][j]<=x){
            addedge(i,j+n,INF);
            addedge(j,i+n,INF);
        }
}

int main(){
    freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
        s=0;t=2*n+1;tot=t+1;all=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&f[i],&p[i]);
            all+=f[i];
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dist[i][j]=LLINF;
        int u,v,w;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&u,&v,&w);
            if (w<dist[u][v])
                dist[u][v]=dist[v][u]=w;
        }
        for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if (dist[i][j]>dist[i][k]+dist[k][j])
                dist[i][j]=dist[i][k]+dist[k][j];
        ans=-1;L=0;R=LLINF-1;
        int maxflow;
        while(L<=R){
            mid=(L+R)>>1;
            add(mid);
            maxflow=dinic(s,t,tot);
            if (maxflow==all){
                ans=mid;
                R=mid-1;
            }
            else L=mid+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}


全部评论

相关推荐

挣K存W养DOG:入职送金条全球游,路过缅甸停一下🐔
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务