设为首页 加入收藏

TOP

POJ 2391Ombrophobic Bovines（二分+最短路+网络流之最大流）
2015-07-24 05:50:27 来源: 作者: 【大 中 小】 浏览:4次
Tags：POJ 2391Ombrophobic Bovines （二分 短路 网络 最大

题目地址：http://poj.org/problem?id=2391

这个题WA了一晚上，原因是数组开小了，然后又TLE了一天，原因是数组改的过大了。。。。不多说什么了。。。

思路不难，建图也不难，二分时间，然后把每个田地之间的最短距离用floyd最短路求出来。然后建立一个源点与汇点，将田地拆分成两个点，在距离之内的进行连边，要单向连边。然后将源点与田地相连，权值为每个田地的牛的数目，再把另一边的田地与汇点相连，权值为每个田地最大可避雨的牛的数目。拆开的田地之间权值可以为无穷大。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            using namespace std; const long long maxint1=1e16; const int maxint=1e9; long long dp[500][500], sum, n; int num[500], d[500], pre[10000], cur[500], q[500],head[100000], s, t, nv, cnt; struct node { int u, v, cap, next; } edge[10000000]; struct filed { int x, y; } ff[300]; 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)); int flow=0, i, u=pre[s]=s; bfs(); 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>=sum) 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() { long long i, a, b, j; long long m, c; //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); scanf("%lld%lld",&n,&m); sum=0; for(i=0; i<=n; i++) { for(j=0; j<=n; j++) { dp[i][j]=maxint1; if(i==j) { dp[i][j]=0; } } } for(i=1; i<=n; i++) { scanf("%d%d",&ff[i].x,&ff[i].y); sum+=ff[i].x; } while(m--) { scanf("%lld%lld%lld",&a,&b,&c); if(dp[a][b]>c) { dp[a][b]=c; dp[b][a]=c; } } floyd(); int x; long long high=200000000000, mid, low=1, ans=-1; while(low<=high) { mid=(high+low)/2; s=0; t=2*n+1; nv=t+1; memset(head,-1,sizeof(head)); cnt=0; for(i=1; i<=n; i++) { add(s,i,ff[i].x); add(i+n,t,ff[i].y); } for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { if(dp[i][j]<=mid) { add(i,j+n,maxint); } } } x=isap(); if(x>=sum) { ans=mid; high=mid-1; } else { low=mid+1; } } printf("%lld\n",ans); return 0; }


【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：UVA 1508 - Equipment 状态压缩 .. 下一篇：自定义集合实体类

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: