Gasoline Gym – 101908G(二分最大流)

题目链接:https://cn.vjudge.net/problem/Gym-101908G
题目大意:有p个加油站,r个炼油厂,加油站分别需要Di的油,炼油厂分别可以供给Ei的油,加油站与炼油厂之间有一些线路,通过这些线路可以将油从炼油厂运送到加油站,运油的卡车数量无限。
解题思路:二分最大流
1. 建图
最大流,最大流就要有源点和汇点,而这道题并没有明显的源点汇点,所以我们人为的添加一个‘0’点做源点,‘n+m+1’做汇点,将炼油厂都与源点相连,流量限制是炼油厂的油量,将所有加油站都与汇点相连,每条连边的流量限制是每个加油站所需的油量,这样一个最大流的网络就构建出来了,
2. 二分
跑最大流用最大流maxflow是否等于需要的总油量来判断是否可以满足所有加油站的需求,在此基础上用二分来限制时间,也就是在限制只有ans及以下长度的路联通的前提下用最大流判断是否可以满足条件,二分ans即可。
代码

#include <iostream>
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n,m,k;
int sum,x[1500],y[1500],u[20020],v[20020],w[20020];
int head[2020],vis[2200],dis[2100],cur[2100],cnt;

struct node
{
    int to,flow,next;
}edge[50000];

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

int bfs(int s,int t)
{
    memset(vis,0x7f,sizeof(vis));
    queue<int>q;
    q.push(s);
    vis[s]=0;
    while(!q.empty())
    {
        s=q.front();
        q.pop();
        for(int i=head[s];i!=-1;i=edge[i].next)
        {
            int to=edge[i].to;
            int flow=edge[i].flow;
            if(flow&&vis[to]>0x7f)
            {
                vis[to]=vis[s]+1;
                q.push(to);
            }
        }
    }
    if(vis[t]<inf)return 1;
    else return 0;
}

int dfs(int s,int t,int limit)
{
    if(!limit||s==t)
        return limit;
    int flow=0,f;
    for(int i=cur[s];i!=-1;i=edge[i].next)
    {
        cur[s]=i;
        if(vis[edge[i].to]==vis[s]+1)
        {
            f=dfs(edge[i].to,t,min(limit,edge[i].flow));
            flow+=f;
            limit-=f;
            edge[i].flow-=f;
            edge[i^1].flow+=f;
            if(!limit)break;
        }
    }
    return flow;
}

int dinic(int s,int t)
{
    int ans=0;
    while(bfs(s,t))
    {
        memcpy(cur,head,sizeof(head));
        ans+=dfs(s,t,inf);
    }
    return ans;
}

int build(int mid)
{
    memset(head,-1,sizeof(head));
    cnt=0;
    for(int i=1;i<=m;i++)//源点
        addedge(0,i,y[i]);
    for(int i=1;i<=n;i++)//汇点
        addedge(i+m,m+n+1,x[i]);
    for(int i=1;i<=k;i++)
    {
        if(w[i]<=mid)
            addedge(v[i],u[i]+m,inf);
    }
    int t=dinic(0,m+n+1);
    if(t==sum)return 1;
    else return 0;
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i];
        sum+=x[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>y[i];
    }
    for(int i=1;i<=k;i++)
    {
        cin>>u[i]>>v[i]>>w[i];
    }
    int l=1,r=1000000,ans=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(build(mid))
        {
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注