poj 2112 Optimal Milking 二分+最大流

<<訓練指南>>P367頁提到的公平分配問題。

二分答案ans

建模：

構造二分圖，奶牛看成X集合，擠奶機看成Y集合。

1、X和源S連邊，邊容量為1.

2、滿足dist(x,y)<=ans的 X和Y連邊，邊容量為1

3、Y和匯T連邊，邊容量為m.(不能超過擠奶機上限)

這樣，網絡中的流量都是由S——》X——》Y——》T點 ，只有當網絡的總流量等於K時，才意味著每一個奶牛都選擇了一個擠奶器，也就是一個可行解。

通過log（n）次的最大流既可以求出答案。

dinic實現。

#include
#include
#include
#include
using namespace std;
#define MAXN 250
#define INF 0x3f3f3f3f
struct edge
{
	int to,c,next;
};
edge e[999999];
int que[MAXN*100];
int dis[MAXN];
int pre[MAXN];
int head[MAXN],head2[MAXN];
int mp[MAXN][MAXN];
int st,ed;
int maxflow;
int en;
int n,m,k,c;
void add(int a,int b,int c)
{
	e[en].to=b;
	e[en].c=c;
	e[en].next=head[a];
	head[a]=en++;
	e[en].to=a;
	e[en].c=0;
	e[en].next=head[b];
	head[b]=en++;
}
bool bfs()
{
	memset(dis,-1,sizeof(dis));
	que[0]=st,dis[st]=1;
	int t=1,f=0;
	while(fmp[i][k]+mp[k][j])
                    mp[i][j]=mp[i][k]+mp[k][j];
            }
        }
    }
}
void build(int mid)
{
    init();
    for(int i=1;i<=k;i++) add(i,ed,m);
    for(int j=k+1;j<=k+c;j++) add(st,j,1);
    for(int i=k+1;i<=k+c;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(mp[i][j]<=mid)
            {
                add(i,j,1);
            }
        }
    }
}
int cal()
{
    l=0;r=20000;
    int ans=0;
    while(l<=r)
    {
        mid=(l+r)>>1;
        build(mid);
        if(dinic()==c) {ans=mid;r=mid-1;}
        else l=mid+1;
    }
    return ans;
}
int main()
{
    while(scanf("%d%d%d",&k,&c,&m)!=EOF)
    {
        input();
        printf("%d\n",cal());
    }
}