POJ 2391 Ombrophobic Bovines 二分拆点最大流+floyd（高精度）

Description

Input

Output

Sample Input

3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120

Sample Output

110

Hint

Source

//2436K	219MS
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inff 200000000007
#define inf 0x3f3f3f
#define M 1007
#define MIN(a,b) a>b?b:a;
using namespace std;
struct E
{
    int v,w,next;
}edg[500000];
int dis[2000],gap[2000],head[2000],nodes;
int sourse,sink,nn;
int cow[M][2],n,s,t,countt;
long long g[M][M],maxx;
void init()
{
    nodes=0;maxx=0,countt=0;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j)g[i][j]=0;
            else g[i][j]=inff;
}
void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(g[i][k]+g[k][j]<g[i][j])
                    g[i][j]=g[i][k]+g[k][j];
}
long long findmin()
{
    long long maxxx=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j&&g[i][j]!=inff)
                maxxx=max(maxxx,g[i][j]);
    return maxxx;
}
void addedge(int u,int v,int w)
{
    edg[nodes].v=v;
    edg[nodes].w=w;
    edg[nodes].next=head[u];
    head[u]=nodes++;
    edg[nodes].v=u;
    edg[nodes].w=0;
    edg[nodes].next=head[v];
    head[v]=nodes++;
}
int dfs(int src,int aug)
{
    if(src==sink)return aug;
    int left=aug,mindis=nn;
    for(int j=head[src];j!=-1;j=edg[j].next)
    {
    	int v=edg[j].v;
    	if(edg[j].w)
        {
           if(dis[v]+1==dis[src])
           {
               int minn=MIN(left,edg[j].w);
               minn=dfs(v,minn);
               edg[j].w-=minn;
               edg[j^1].w+=minn;
               left-=minn;
               if(dis[sourse]>=nn)return aug-left;
               if(left==0)break;
           }
           if(dis[v]<mindis)
           mindis=dis[v];
        }
    }

        if(left==aug)
        {
            if(!(--gap[dis[src]]))dis[sourse]=nn;
            dis[src]=mindis+1;
            gap[dis[src]]++;
        }
        return aug-left;
}
int sap(int s,int e)
{
    int ans=0;
	nn=e+1;
    memset(dis,0,sizeof(dis));
    memset(gap,0,sizeof(gap));
    gap[0]=nn;
    sourse=s;
    sink=e;
    while(dis[sourse]<nn)
    ans+=dfs(sourse,inf);
    return ans;
}
bool search(long long mid)
{

    s=0,t=n+n+1,nodes=0;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)
    {
        addedge(s,i,cow[i][0]);
        addedge(i+n,t,cow[i][1]);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(g[i][j]<=mid)
                addedge(i,j+n,inf);
    if(sap(s,t)==countt)return true;
    return false;
}
long long solve()
{
    long long l=0,r=maxx,mid,ans=-1;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(search(mid)){ans=mid;r=mid-1;}
        else l=mid+1;
    }
    return ans;
}
int main()
{
    int m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        int a,b;
        long long c;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&cow[i][0],&cow[i][1]);
            countt+=cow[i][0];
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%lld",&a,&b,&c);
            if(g[a][b]>c)g[a][b]=g[b][a]=c;
        }
        floyd();
        maxx=findmin();
        printf("%lld\n",solve());
    }
    return 0;
}