http://poj.org/problem?id=2391
floyd+网络流+二分
题意：有一个有向图，里面每个点有ai头牛，快下雨了牛要躲进雨棚里，每个点有bi个雨棚，每个雨棚只能躲1头牛。牛可以通过点之间的边移动来躲到其他的点的雨棚，路很宽一次可以走无数头牛，路的权是牛走过这条路要的时间。求最短需要多少时间所有牛都躲到雨棚下。
题解：
先floyd求出每个点到每个点的最短时间！然后二分答案，也就是二分牛躲完的时间，然后大于这个时间的路都封了，建个碉图，每个点分成两个点A和B，起点连接到所有的A，流量为牛数，所有的点B连接到终点，流量为棚数，一些A连接到一些B，流量为无限，代表牛的移动。二分+网络流，啪啪啪就过了。这是我做的第一个二分+网络流的题，好激动口牙！
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const long long inf=0x7fffffffffffLL;
const int MAXN=;
long long a[MAXN][MAXN];
long long b[MAXN][MAXN];
long long d[MAXN][MAXN];
int m,n;
ll c[MAXN][MAXN];
ll D[MAXN],h[MAXN],g[MAXN];
bool found;
ll augc,flow;
int st,ed,N;
ll sum; void floyd()
{
int i,j,k;
memcpy(d,b,sizeof(b));
for(k=;k<=n;k++)
for(i=;i<=n;i++)
for(j=;j<=n;j++)
if(d[i][k]+d[k][j]<d[i][j])
d[i][j]=d[i][k]+d[k][j];
} void aug(const int m)
{
int i,augco=augc,mini,minh=N-;
if (m==ed)//如果当前结点为汇点
{
found=true;
flow+=augc; //增加流量
return;
}
for (i=D[m]; i<=N; i++)//寻找容许边
if (c[m][i]> && h[i]+==h[m])//如果残留容量大于0，如果是容许边
{
if (c[m][i]<augc) augc=c[m][i];//如果容许边流量小于当前增广路流量 则更新增广路流量
D[m]=i; //把i定为当前弧
aug(i); //递归
if (h[]>=N) return; //GAP 如果源点距离标号大于n 则停止算法
if (found) break; //如果找到汇点 则退出寻找
augc=augco;//没找到就还原当前的流
}
if (!found) //重标号
{
for (i=; i<=N; i++) //找那个标号，这里不能用d[m]开始，不然会蛋疼
if (c[m][i]> && h[i]<minh)
{
minh=h[i];
mini=i;
}
g[h[m]]--; //GAP 距离为
if (g[h[m]]==) h[]=N; //GAP
h[m]=minh+;
D[m]=mini;
g[h[m]]++; //GAP
}
else
{//修改残量
c[m][i]-=augc;
c[i][m]+=augc;
}
} bool farm(ll time)
{
int i,j;
//cout<<"farm"<<time<<endl;
memcpy(c, a, sizeof(a));
for(i=;i<=n;i++)
for(j=;j<=n;j++)
if(d[i][j]<=time) c[i+][j++n]=inf;
else c[i+][j++n]=;
N=ed;
// for(i=1;i<=N;i++)
// {
// for(j=1;j<=N;j++)
// cout<<c[i][j]<<' ';
// cout<<endl;
// }
memset(h,,sizeof(h));
memset(g,,sizeof(g));
g[]=N;
flow=;
for(i=; i<=N; i++)
D[i]=;//当前弧初始化
while(h[]<N)
{
augc=inf;//初始化增广路容量为正无穷大
found=false;
aug();//从源点开始找
}
if(flow==sum) return true;
else return false;
} int main()
{
int i,j,k;
ll x,y,z;
while(scanf("%d%d",&n,&m)!=EOF)
{
sum=;
memset(a,,sizeof(a));
st=;ed=n+n+;
for(i=;i<=n+;i++)
{
scanf("%lld%lld",&x,&y);
sum+=x;
a[][i]+=x;
a[i+n][ed]+=y;
}
for(i=;i<=n;i++)
for(j=;j<=n;j++)
b[i][j]=inf;
for(i=;i<=n;i++)
b[i][i]=;
for(i=;i<=m;i++)
{
scanf("%lld%lld%lld",&x,&y,&z);
b[x][y]=min(b[x][y],z);
b[y][x]=b[x][y];
}
floyd();
ll l=inf,r=-;
for(i=;i<=n;i++)
for(j=;j<=n;j++)
{
l=min(l,d[i][j]);
r=max(r,d[i][j]);
}
r=min(inf-,r);
if (!farm(r))
{
printf("-1\n");
continue;
}
ll mid=(l+r)/,pl=-,pr=-;
while(l!=pl || r!=pr)
{
pl=l;pr=r;
if(farm(mid)) r=mid;
else l=mid;
mid=(l+r)/;
//cout<<l<<','<<r<<','<<mid<<endl;
}
printf("%lld\n",r);
}
return ;
}