poj2391

链接：http://poj.org/problem?id=2391

题解：

二分答案，变成判定性问题，只需把能经过的边在当前图中联通

另外对牛和牛棚要拆点

代码：

#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <iostream>  
#include <vector>  
#include <queue>  
using namespace std;
#define ll long long
const int maxn=1e6;
const int maxn2=500;
#define INF 1e16
#define INF2 1e9
int n,m,s,t,l,sum,ax;
int head[maxn2],head2[maxn2],d[maxn2],cow[maxn2],cap[maxn2];
ll dis[maxn2][maxn2];
bool vis[maxn2];
struct re{
    int a,b,c,flow;
}a[maxn];
void arr(int x,int y,int z)
{
    a[++l].a=head[x];
    ax=max(ax,l);
  a[l].b=y;
    a[l].c=z;
    a[l].flow=0;
    head[x]=l;
}
queue<int> q;
bool bfs(){
    memset(vis,0,sizeof(vis));
    q.push(s);
    d[s]=0; vis[s]=1;
    while (!q.empty())
    {
        int x=q.front();q.pop();
        int u=head[x];
        while (u)
        {
            int v=a[u].b;
            if (!vis[v]&&a[u].c>a[u].flow)
            {
                vis[v]=1;
                d[v]=d[x]+1;
                q.push(v);
            }
            u=a[u].a;
        }
    }
    return(vis[t]);
}
int dfs(int x,int y)
{
    if (x==t||y==0) return y;
    int flow=0,f,tmp;
    int u=head[x];
    while (u)
    {
        int v=a[u].b;
        if (d[x]+1==d[v]&&(f=dfs(v,min(y,a[u].c-a[u].flow)))>0)
        {
            a[u].flow+=f;
            if (u%2) tmp=u+1; else tmp=u-1;
            a[tmp].flow-=f;
            flow+=f; 
            y-=f;
            if (y==0) break;
        }
        u=a[u].a;
    }
    head[x]=u;
    return(flow);
}
int maxflow()
{
    int flow=0;
    while (bfs())
    {
        flow+=dfs(s,INF2);
        memcpy(head,head2,sizeof(head2));
    }
    return(flow);
}
void floyd()
{
    for (int k=1;k<=n;k++)
      for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
          if (i!=j)
          dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
void buildedge(ll x)
{
  memset(head,0,sizeof(head));l=0;
    for (int i=1;i<=n;i++)
    {
        arr(0,i,cow[i]); arr(i,0,0);
        arr(i+n,n*2+1,cap[i]); arr(n*2+1,i+n,0);
        arr(i,i+n,INF2); arr(i+n,i,0);
    } 
    for (int i=1;i<=n;i++)
      for (int j=1;j<=n;j++)
        if (dis[i][j]<=x)
        {
          arr(i,j+n,INF2); arr(j+n,i,0); 
        }
}
ll solve()
{
    ll ans=-1,h=1,t=INF-1000;
    while (h<=t)
    {
        ll mid=(h+t)/2; 
        buildedge(mid); memcpy(head2,head,sizeof(head));
        if (maxflow()>=sum)
        {
            ans=mid; t=mid-1;
        } else h=mid+1;
    }
    return ans; 
}
int main()
{
    freopen("noip.in","r",stdin);
    freopen("noip.out","w",stdout);
    std::ios::sync_with_stdio(false);
    while (cin>>n>>m)
    {
        sum=0; s=0; t=2*n+1;
        for (int i=1;i<=n;i++)
        {
            cin>>cow[i]>>cap[i];
            sum+=cow[i];
        }
        for (int i=1;i<=n;i++)
          for (int j=1;j<=n;j++)
            dis[i][j]=INF;
        ll a,b,c;
        for (int i=1;i<=m;i++)
        {
            cin>>a>>b>>c;
            dis[a][b]=min(dis[a][b],c);
            dis[b][a]=min(dis[b][a],c);
        }
        floyd();
        cout<<solve()<<endl;
    } 
    return 0;
}