首页 > 代码库 > ●POJ poj 2112 Optimal Milking

●POJ poj 2112 Optimal Milking

●题目大意:

给出K个挤奶机器(编号1~K),C头牛(编号K+1~K+C)(机器和牛各在不同的地方)和每台机器最多可M头牛挤奶;

然后以邻接矩阵告诉各点间的直接距离(不同的地方间若直接距离等于0,则表明没有直接连路)。

目的是要让每一头牛都要去一台机器处被挤奶,要使行走路程最大的牛的路程最小。goto

●题解:

刚拿到题时很Mengbi,搞了一段时间后才发现每个点可以去多次……

因为点数只有不超过230个,那么我们可以求出每个牛到每个机器的最短距离(自然是floyd嘛),那么问题变成了将牛分配至机器,不同的牛分配到不同的机器有不同的代价(即计算出的最短距离),且每个机器的能接受的牛的数量有限,要求出最大代价的最小值(明摆着套路二分答案嘛)。

至此,思路渐渐清晰,先floyd求每个牛到每个机器的最短距离,然后二分答案(lim 表示),开始建图,跑网络流;

建图&网络流(对于每一个二分出来的lim):

1、源点 s 向各头牛连一条容量为1的有向边;

2、枚举牛和机器的”组合“,若 A 牛到 B 机器的(最短)距离小于 lim ,则从 A 向 B 连一条容量为 inf(只要容量大于0即可) 的有向边;

3、从各机器向源点 E 连一条容量为1的有边;

4、用最大流求图中的流量,若流量等于牛的数量,就,咳咳.…..

总:floyd+二分+最大流

#include<cstdio>
#include<cstring>
#include<iostream>
#define oo (0x3f3f3f3f)
using namespace std;
struct edge{
	int to,next,cap;
}e[250*250*2];
int mp[250][250],head[250],q[250],d[250];
int k,c,m,l=+oo,r=-1,mid,ent;
void add(int u,int v,int cap){
	e[ent]=(edge){v,head[u],cap};head[u]=ent++;
	e[ent]=(edge){u,head[v],0};head[v]=ent++;
}
bool bfs(int s,int t)
{
	int ll=0,rr=1; q[rr]=s; 
	memset(d,0,sizeof(d)); d[s]=1; 
	while(ll<rr)
	{
		ll++; int u=q[ll];
		for(int i=head[u];~i;i=e[i].next) if(e[i].cap>0)
		{
			int v=e[i].to; if(d[v]) continue;
			d[v]=d[u]+1; q[++rr]=v;
		}
	}
	return d[t];
}
int dfs(int u,int t,int flow)
{
	if(u==t) return flow; int flowout=0,f;
	for(int i=head[u];i!=-1;i=e[i].next)
	{
		int v=e[i].to;
		if(d[v]!=d[u]+1) continue;
		f=dfs(v,t,min(flow,e[i].cap));
		flowout+=f; flow-=f;
		e[i].cap-=f; e[i^1].cap+=f;
		if(flow==0) break;
	}
	return flowout;
}
bool check(int s,int t)
{
	memset(head,-1,sizeof(head));ent=0;
	for(int i=k+1;i<=k+c;i++)
	  for(int j=1;j<=k;j++) 
	  	if(mp[i][j]>-1&&mp[i][j]<=mid) add(i,j,1);
	for(int i=k+1;i<=k+c;i++) add(s,i,1);
	for(int i=1;i<=k;i++) add(i,t,m); 
	int flow=0;
	while(bfs(s,t)) flow+=dfs(s,t,+oo);
	return flow==c; 
}
void solve(int s,int t)
{
	int ans=0;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(check(s,t)) ans=mid,r=mid-1;	else l=mid+1;
	}
	printf("%d",ans);
}
void floyd()
{
	for(int o=1;o<=k+c;o++)
	  for(int i=1;i<=k+c;i++)
		for(int j=1;j<=k+c;j++)
			if(mp[i][o]>-1&&mp[o][j]>-1&&(mp[i][j]==-1||mp[i][o]+mp[o][j]<mp[i][j]))
				mp[i][j]=mp[i][o]+mp[o][j];
	for(int i=k+1;i<=k+c;i++)
	  for(int j=1;j<=k;j++)
	   	l=0,r=max(r,mp[i][j]);
}
int main()
{
	scanf("%d%d%d",&k,&c,&m);
	memset(mp,-1,sizeof(mp));
	for(int i=1;i<=k+c;i++) for(int j=1;j<=k+c;j++) 
	{
		scanf("%d",&mp[i][j]);
		if(mp[i][j]==0&&i!=j) mp[i][j]=-1;	
	}	
	floyd(); solve(0,k+c+1); 
	return 0;
}

●POJ poj 2112 Optimal Milking