poj2391 最大流+拆点

题意:F块草坪，上面有n头牛，可以容纳m个牛遮雨。将草坪一份为2，成为二部图。

对于此题，和poj2112很像，只是2112很明显的二部图。这道题就开始敲，但是建图遇到问题，草坪的2个值怎么处理，于是将1个草坪分成2分，一份与源点相连，值为牛的个数，

另一份与汇点相连表示可以留下多少牛，由于是一个草坪，所以这两份之间相连，容量无穷大。然后对于能够相通的2块草坪，由当前块草坪左边部分，向相连的连（前提时间小于二分的时间），容量无穷。二分答案。

#include<stdio.h>

#include<string.h>

#include<queue>

#define maxn 600

#define INF 10000000000000

#define LL __int64

using namespace std;

int vis[maxn],n,m,c[maxn],f[maxn],fn;

LL map[maxn][maxn],dis[maxn][maxn];

LL min(LL x,LL y)

{return x<y?x:y;}

LL max(LL x,LL y)

{return x>y?x:y;}

void init()

{

    int i,j;

    for(i=;i<=fn;i++)

    {

        for(j=;j<=fn;j++)

        {

            if(i==j)

                dis[i][j]=;

            else

                dis[i][j]=INF;

        }

    }

}

void floyd()

{

    int i,j,k;

    for(k=;k<=fn;k++)

        for(i=;i<=fn;i++)

            for(j=;j<=fn;j++)

            {

                if(dis[i][j]>dis[i][k]+dis[k][j])

                    dis[i][j]=dis[i][k]+dis[k][j];

            }

    /*for(i=1;i<=fn;i++)

    {

        for(j=1;j<=fn;j++)

        {

            printf("%d ",dis[i][j]);

        }

        printf("\n");

    }*/

}

void makemap(LL maxval)

{

    int i,j;

    memset(map,,sizeof(map));

    for(i=;i<=fn;i++)

    {

        map[][i]=c[i];

    }

    for(i=;i<=fn;i++)

        map[i+fn][n+]=f[i];

    for(i=;i<=fn;i++)

        map[i][i+fn]=INF;

    for(i=;i<=fn;i++)

    {

        for(j=;j<=fn;j++)

        {

            if(i==j)

                continue;

            if(dis[i][j]<=maxval)

            {

                map[i][j+fn]=INF;

            }

        }

    }

    /*for(i=0;i<=n+1;i++)

    {

        for(j=0;j<=n+1;j++)

        {

            printf("%d ",map[i][j]);

        }

        printf("\n");

    }*/

}

int BFS()

{

    int i,j;

    queue<int>q;

    memset(vis,-,sizeof(vis));

    vis[]=;

    q.push();

    while(!q.empty())

    {

        int t=q.front();

        q.pop();

        for(i=;i<=n+;i++)

        {

            if(vis[i]<&&map[t][i])

            {

                vis[i]=vis[t]+;

                q.push(i);

            }

        }

    }

    if(vis[n+]>)

        return ;

    return ;

}

LL dfs(int u,LL low)

{

    int i,j;

    LL a;

    if(u==n+)

        return low;

    for(i=;i<=n+;i++)

    {

        if(vis[i]==vis[u]+&&map[u][i])

        {

            a=(LL)dfs(i,min(low,map[u][i]));

            if(!a)continue;

            map[u][i]-=a;

            map[i][u]+=a;

            return a;

        }

    }

    return ;

}

int main()

{

    int i,j,num;

    LL maxval;

    while(scanf("%d%d",&fn,&m)!=EOF)

    {

        num=;

        maxval=;

        for(i=;i<=fn;i++)

        {

            scanf("%d%d",&c[i],&f[i]);

            num+=c[i];

        }

        n=fn*;

        init();

        for(i=;i<m;i++)

        {

            LL x,y,z;

            scanf("%I64d %I64d %I64d",&x,&y,&z);

            if(dis[x][y]>z)

            {

                dis[y][x]=z;

                dis[x][y]=z;

            }

        }

        floyd();

        for(i=;i<=fn;i++)

        {

            for(j=;j<=fn;j++)

            {

                if(dis[i][j]!=INF)

                    maxval=max(maxval,dis[i][j]);

            }

        }

        LL l=,r=maxval,ans=-;

        while(l<=r)

        {

            LL ret=;

            LL mid=(l+r)/;

            makemap(mid);

            while(BFS())

            {

                while()

                {

                    LL a=dfs(,INF);

                    if(!a)break;

                    ret+=a;

                }

            }

            //printf("%d ",mid);

            if(ret>=num)

            {

                ans=mid;

                r=mid-;

            }

            else

                l=mid+;

        }

        printf("%I64d\n",ans);

    }

}