注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

poj2112Optimal Milking题解  

2014-03-25 20:58:17|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

最优挤奶

BY   LGS

题目大意:给你K个机器,N头奶牛要去机器挤奶,每个机器和奶牛之间有路相连.确定一种方案,使每头牛都到达机器,且每头牛所有路程的最大值最小.输出这个最大值.

 

题解:难题,我看了题解才会做.首先,给定的牛和机器的距离不一定是最短的,FOLYED是必须的.其次,对于答案,直接算实在太难了,不妨换个角度,我们2分枚举这个答案,然后进行验证.最后,验证需要构图,即变成了最大匹配问题,如果二分的mid>奶牛与机器之间的路,那么这条路可以存在,容量为1.否则不存在,容量为0.一开始为了方便,可以设个源点,源点到奶牛的距离为1,一个汇点,机器到汇点的距离为2.因为机器可以用两次,最大流构图即可.

 

总结:FOLY+最大流+二分答案.

 

代码:

#include<cstdio>
#include<cstring>
#define maxn 300
#define maxx 9999999
using namespace std;
int k,i,j,c,m,n,sum,u,path,tot,totl,r,l,mid;
int dis[maxn][maxn],f[maxn][maxn],flow[maxn],pre[maxn];
bool vist[maxn];
int max(int a,int b){return (a>b)?a:b;}
int min(int a,int b){return (a>b)?b:a;}
void floyed()
 {int i,j,u;
  for (u=1;u<=n;u++)for (i=1;i<=n;i++)for (j=1;j<=n;j++)
   if (u!=i&&i!=j&&j!=u) dis[i][j]=min(dis[i][j],dis[i][u]+dis[u][j]);
 }
bool pan(int w)
 {
 int i,j,sum;
 memset(f,0,sizeof(f));
  for (i=1;i<=k;i++) f[0][i]=m;
 for (i=k+1;i<=k+c;i++) f[i][n]=1;
 for (i=1;i<=k;i++)
  for (j=k+1;j<=k+c;j++) if (dis[i][j]<=w) f[i][j]=1;
 sum=0;
  while (1){
 memset(flow,0,sizeof(flow));memset(pre,-1,sizeof(pre));
 memset(vist,false,sizeof(vist));flow[0]=maxx; 
 while (1){
          tot=0;
          totl=-1;
     for (i=0;i<=n;i++) if ((flow[i]>tot)&&(!vist[i]))
                {tot=flow[i];totl=i;}
          if ((totl==-1)||(totl==n)) break;
          vist[totl]=true;
          for (i=0;i<=n;i++)if (i!=totl)
                if (flow[i]<min(f[totl][i],tot))
                 {
                 flow[i]=min(f[totl][i],tot);
                 pre[i]=totl;
                 } 
          }
      if (totl==-1) break;
      path=flow[n];
      sum+=path;
      i=n;
      while (i!=-1){
               j=pre[i];
               f[i][j]+=path;
               f[j][i]-=path;
               i=j;
               }   
           }
 if (sum==c) return true;
 return false;
 }
int main()
{
 scanf("%d%d%d",&k,&c,&m);
 n=k+c;
 for (i=1;i<=n;i++)
  for (j=1;j<=n;j++)
       {scanf("%d",&dis[i][j]);
        if (!dis[i][j]) dis[i][j]=maxx;
       }
 floyed();n++;l=0;r=5700;
 while (l+1<r)
         {
         mid=(l+r)>>1;
         if (pan(mid))r=mid;
                else  l=mid+1;
         }
if (pan(l))r=l;
printf("%d",r);
return 0;
}
  评论这张
 
阅读(30)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018