POJ2112Optimal Milking（二分+floyd最短路+网络流） - c++编程基础

TOP

POJ2112Optimal Milking（二分+floyd最短路+网络流）

2015-07-24 05:51:48 来源: 作者: 【大中小】浏览:4次

Tags：POJ2112Optimal Milking （二分 floyd 短路网络

最近忙着预习课本备考，没怎么刷题，（我是真的有在好好看书。。）不敲题还是手痒痒，马上就邀请赛了，还是每晚睡觉前都拿来刷题吧。白天的时间足够了。

话说这题调了一晚上。。。一直以为是几天没敲状态下滑。。（虽然也没几天。。）当发现错误的时候才发现原来是少敲了个字母。。。而且我一般很少在bfs的那个地方出错，错误地方也很隐蔽。。所以找了一晚上，真是敲错一个字母成千古恨。

这题大概是职业生涯目前为止敲得最长的一道算法题了。。（模拟题除外。。）先后用了二分（二分最大距离），求最短路（找机器与牛之间的最短距离），以及网络流isap（判断能否满流，满流说明此时所有牛都可以吃到食物）。

建图思路是，建立一个超级源点与超级汇点，将机器与超级源点相连，权值为每台机器的最大供应量，将牛与超级汇点相连，权值为1，若牛与机器的最短距离小于等于二分到的最大距离，则连边。权值为1.然后判断是否满流。每次二分都需要求一次最大流，并判断是否满流。最终的最小值就是所要求的答案。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include
          #include 
          
            using namespace std; int dp[300][300], head[300], s, t, nv, maxint=99999999, cnt, n, c; int num[300], d[300], pre[300], q[300], cur[300]; struct node { int u, v, cap; int next; }edge[1000000]; void add(int u, int v, int cap) { edge[cnt].v=v; edge[cnt].cap=cap; edge[cnt].next=head[u]; head[u]=cnt++; edge[cnt].v=u; edge[cnt].cap=0; edge[cnt].next=head[v]; head[v]=cnt++; } void floyd() { int i, j, k; for(k=1;k<=n;k++) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(dp[i][j]>dp[i][k]+dp[k][j]) { dp[i][j]=dp[i][k]+dp[k][j]; } } } } } void bfs() { memset(num,0,sizeof(num)); memset(d,-1,sizeof(d)); int f1=0, f2=0, i; d[t]=0; num[0]=1; q[f1++]=t; while(f1>=f2) { int u=q[f2++]; for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(d[v]==-1) { d[v]=d[u]+1; num[d[v]]++; q[f1++]=v; } } } } int isap() { memcpy(cur,head,sizeof(cur)); bfs(); int flow=0, u=pre[s]=s, i; while(d[s]
           
            edge[cur[i]].cap) { f=edge[cur[i]].cap; pos=i; } } for(i=s;i!=t;i=edge[cur[i]].v) { edge[cur[i]].cap-=f; edge[cur[i]^1].cap+=f; } flow+=f; if(flow>c) return flow; u=pos; } for(i=cur[u];i!=-1;i=edge[i].next) { if(d[edge[i].v]+1==d[u]&&edge[i].cap) { break; } } if(i!=-1) { cur[u]=i; pre[edge[i].v]=u; u=edge[i].v; } else { if(--num[d[u]]==0) break; int mind=nv; for(i=head[u];i!=-1;i=edge[i].next) { if(mind>d[edge[i].v]&&edge[i].cap) { mind=d[edge[i].v]; cur[u]=i; } } d[u]=mind+1; num[d[u]]++; u=pre[u]; } } return flow; } int main() { int k, m, i, j, x, ans; while(scanf(%d%d%d,&k,&c,&m)!=EOF) { n=k+c; for(i=1;i<=k+c;i++) { for(j=1;j<=k+c;j++) { scanf(%d,&dp[i][j]); if(dp[i][j]==0) dp[i][j]=maxint; } } floyd(); /*for(i=1;i<=k;i++) { for(j=1;j<=c;j++) { printf(%d ,dp[i][j+k]); } printf( ); }*/ int high=400000, mid, low=1; while(low<=high) { mid=(high+low)/2; s=0; t=n+1; nv=t+1; memset(head,-1,sizeof(head)); cnt=0; for(i=1;i<=k;i++) { add(s,i,m); } for(i=1;i<=c;i++) { add(k+i,t,1); } for(i=1;i<=k;i++) { for(j=1;j<=c;j++) { if(dp[i][k+j]<=mid) { add(i,k+j,1); } } } x=isap(); //printf(%d ,x); //return 0; if(x>=c) { ans=mid; high=mid-1; } else if(x
            
             ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 1698 Alice's Chance 拆..	下一篇：二、C++迭代器的两种实现方式（R..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: