【Usaco05Mar】Ombrophobic Bovines

来源和评测点

USACO 2005 March Gold
Bzoj1738
Poj2391
Caioj1118

题目

【题目大意】
下雨了，有F(1<=F<=200)个牛棚，这F个牛棚之间有P(1<=P<=1500)条无向边（有耗时）
每个牛棚有两个值A和B（A表示一开始这个牛棚有A头牛，B表示下雨时该牛棚最多可以容纳B头牛躲雨）。
问最少需要提前多少时间响“下雨警告”才能让所有牛在下雨前都能够找到可以遮雨的地方。

重点句：
The paths are wide,so that any number of cows can traverse a path in either direction. 无向边
Fields are small compared to the paths and require no time for cows to traverse. 将牛棚看作点
【输入格式】
两个整数: F 和 P
接下来F行，第i行两个整数A和B（A、B的范围都是:0..1000）描述第i个牛棚
接下来P行，每行三个整数。X Y L，表示牛棚X和牛棚Y之间有一条边，耗时是L（1<=L<=1,000,000,000）
【输出格式】
输出一行，即为最短的时间，如果无法使得所有牛都能够有地方避雨，那么输出 “-1”
【输入样例】
3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120
【输出样例】
110
【样例解释】
牛棚1安排4头牛到牛棚2，牛棚1再安排1头牛走到牛棚2，再走到牛棚3避雨。

分析

网络流教程和题目分类参见：
【OI之路】03图论算法-4网络流
其他网络流题目参见：Tag-网络流
本题入选了好题：Tag-好题

这道题建议大家像我一样仔细想想，
别急着看题解，虽然你到我这个页面很可能是来膜题解的

由于边比较复杂，但又是无向图
考虑Floyd获得两点之间最短耗时
然后两点之间只存在一条边了

原问题转化成：
选一些边来满足条件并且最长边最小
条件为牛跑来跑去后每个牛棚能容纳下

考虑二分答案，从而得到满足的边，跑一遍网络流验证解的可行性

构图：
从汇点到各个左牛棚，容量是每个牛棚原本的牛数量
拆点，从左牛棚连到右牛棚，表示可以通过去，容量是无限
从右牛棚到汇点，容量是牛棚最后的最大容纳

假如最大流=牛的数量F 表示可行

记得自己可以连自己

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;

const int INF=0x3f3f3f3f;
int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;}

const int MAXN=510,MAXM=110000;
struct pt
{
    int h;
    int hou;
}p[MAXN];
struct rod
{
    int y,c,g;
    int oth;
}e[MAXM];
int ln;
void ins(int x,int y,int c)
{
    ln++;
    e[ln].y=y;e[ln].c=c;
    e[ln].g=p[x].hou;p[x].hou=ln;

    ln++;
    e[ln].y=x;e[ln].c=0;
    e[ln].g=p[y].hou;p[y].hou=ln;

    e[ln-1].oth=ln;e[ln].oth=ln-1;
}
int st,ed;
int lst[MAXN];
bool bfs()
{
    for(int i=1;i<=ed;i++) p[i].h=0;

    int tou=1,wei=1;
    lst[1]=st;p[st].h=1;
    while(tou<=wei)
    {
        int x=lst[tou];
        for(int k=p[x].hou;k>0;k=e[k].g)
        {
            int y=e[k].y;
            if(p[y].h==0 and e[k].c>0)
            {
                p[y].h=p[x].h+1;
                lst[++wei]=y;
            }
        }
        tou++;
    }
    return p[ed].h>0;
}
int dfs(int x,int f)
{
    if(x==ed) return f;
    int t=0;
    for(int k=p[x].hou;k>0;k=e[k].g)
    {
        int y=e[k].y;
        if(p[y].h==p[x].h+1 and e[k].c>0 and t<f)
        {
            int tt=dfs(y,mymin(f-t,e[k].c));
            t+=tt;e[k].c-=tt;e[e[k].oth].c+=tt;
        }
    }
    if(t==0) p[x].h=0;
    return t;
}
/*
1~n     左牛棚
n+1~n+n 右牛棚
n+n+1   源点
n+n+2   汇点
*/
int n;
int alc;
int aa[MAXN],bb[MAXN];
ll cst[MAXN][MAXN];
bool check(ll mid)
{
    ln=0;for(int i=1;i<=ed;i++) p[i].hou=0;

    for(int i=1;i<=n;i++)
    {
        ins(st,i,aa[i]);ins(i,n+i,INF);ins(n+i,ed,bb[i]);
        for(int j=1;j<=n;j++) if(cst[i][j]<=mid) ins(i,n+j,INF);
    }

    int ans=0;
    while(bfs()) ans+=dfs(st,INF);
    //printf("mid=%d ans=%d alc=%d\n",mid,ans,alc);
    return ans==alc;
}

int main()
{
    memset(cst,63,sizeof(cst));

    int m;scanf("%d%d",&n,&m);
    st=n+n+1,ed=n+n+2;

    for(int i=1;i<=n;i++) scanf("%d%d",&aa[i],&bb[i]),alc+=aa[i];
    for(int i=1;i<=m;i++)
    {
        int x,y;ll c;scanf("%d%d%lld",&x,&y,&c);
        if(c<cst[x][y]) cst[x][y]=cst[y][x]=c;
    }

    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                ll nt=cst[i][k]+cst[k][j];
                if(nt<cst[i][j]) cst[i][j]=nt;
            }

    ll l=0,r=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i-1;j++)
            if(cst[i][j]!=cst[0][0] and cst[i][j]>r) r=cst[i][j];

    ll ans=-1;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }

    printf("%lld",ans);
}