POJ 2112 Optimal Milking 二分最大流

Description

Input

Output

Sample Input

2 3 2
0 3 2 1 1
3 0 3 2 0
2 3 0 1 0
1 2 1 0 2
1 0 0 2 0

Sample Output

2

Source

//808K	94MS
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 10000000
#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 g[307][307],n,m,k,max_dis,s,t;
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;
}
void floyd()
{
    for(int k=1;k<t;k++)
        for(int i=1;i<t;i++)
            for(int j=1;j<t;j++)
                if(g[i][j]>g[i][k]+g[k][j])
                    g[i][j]=g[i][k]+g[k][j];
}
bool build(int mid)
{
    memset(head,-1,sizeof(head));
    nodes=0;
    for(int i=1;i<=n;i++)
        addedge(s,i,k);
    for(int i=1;i<=m;i++)
        addedge(n+i,t,1);
    for(int i=1;i<=n;i++)
        for(int j=1+n;j<t;j++)//这个地方忘记+n，错了一下午
            if(g[i][j]<=mid)
                addedge(i,j,1);
    if(sap(s,t)>=m)return true;
    return false;
}
int solve()
{
    int l=0,r=max_dis,mid,ans;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(build(mid)){ans=mid;r=mid-1;}
        else l=mid+1;
    }
    return ans;
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        s=0,t=n+m+1;
        max_dis=0;
        for(int i=1;i<t;i++)
            for(int j=1;j<t;j++)
            {
                scanf("%d",&g[i][j]);
                if(!g[i][j])g[i][j]=inf;
            }
        floyd();
        for(int i=1;i<t;i++)
            for(int j=1;j<t;j++)
                if(g[i][j]!=inf)
                    max_dis=max(max_dis,g[i][j]);
        int anss=solve();
        printf("%d\n",anss);
    }
    return 0;
}