首页 > 代码库 > Optimal Milking

Optimal Milking

2024-07-19 21:18:21   227人阅读

poj2112:http://poj.org/problem?id=2112

题意：K台挤奶机器，C头牛，K不超过30，C不超过200，每台挤奶机器最多可以为M台牛工作，给出这些牛和机器之间，牛和牛之间，机器与机器之间的距离，在保证让最多的牛都有机器挤奶的情况下，给出其中最长的一头牛移动的距离的最小值。

题解：首先用Floyd求出任意两点之间的最短距离，然后再用二分法限定最多的移动距离d，在求最大流时，搜索增广路的时候同时也判断距离有没有超过d就行了。

  1 #include<cstring>  2 #include<iostream>  3 #include<cstdio>  4 #include<algorithm>  5 #include<queue>  6 using namespace std;  7 int map[301][301];  8 const int INF=100000000;  9 struct Node{ 10     int c; 11     int f; 12 }ma[301][301]; 13 int m,c,knum,pre[301]; 14 int sx,se; 15 void Floy(){ 16     for(int k=1;k<=knum+c;k++) 17        for(int i=1;i<=c+knum;i++) 18            for(int j=1;j<=c+knum;j++){ 19                if(k!=i&&i!=j&&k!=j&&map[i][k]+map[k][j]<map[i][j]) 20                    map[i][j]=map[i][k]+map[k][j]; 21            } 22 } 23 bool  BFS(){ 24     memset(pre,0,sizeof(pre)); 25     queue<int>Q; 26     Q.push(sx); 27     pre[sx]=1; 28     while(!Q.empty()){ 29         int d=Q.front(); 30         Q.pop(); 31         for(int i=0;i<=knum+c+1;i++){ 32             if(!pre[i]&&ma[d][i].c-ma[d][i].f){ 33             pre[i]=pre[d]+1; 34             Q.push(i); 35             } 36         } 37     } 38     return pre[se]!=0; 39 } 40 int dinic(int pos,int flow){ 41     int f=flow; 42      if(pos==se) 43        return flow; 44      for(int i=0;i<=c+knum+1;i++){ 45            if(ma[pos][i].c-ma[pos][i].f&&pre[i]==pre[pos]+1){ 46                 int a=ma[pos][i].c-ma[pos][i].f; 47                 int t=dinic(i,min(a,flow)); 48                 ma[pos][i].f+=t; 49                 ma[i][pos].f-=t; 50                 flow-=t; 51                 if(flow<=0)break; 52                 } 53        } 54        if(f-flow<=0)pre[pos]=-1; 55     return f-flow; 56 } 57 int sum(){ 58      int s=0; 59     while(BFS()) 60        s+=dinic(sx,INF); 61        return s; 62 } 63 void build(int maxn){ 64     memset(ma,0,sizeof(ma)); 65    for(int i=knum+1;i<=knum+c;i++) 66          ma[0][i].c=1; 67    for(int i=1;i<=knum;i++) 68          ma[i][se].c=m; 69    for(int i=knum+1;i<=c+knum;i++) 70        for(int j=1;j<=knum;j++){ 71               if(map[i][j]<=maxn) 72                   ma[i][j].c=1; 73            } 74 } 75 int dinic2(int maxn) { 76     int maxflow; 77     int low=0,mid,up=maxn; 78     while(low<=up){ 79         mid=(low+up)>>1; 80        build(mid); 81         maxflow=0; 82        maxflow=sum(); 83         if(maxflow<c)low=mid+1; 84         else 85             up=mid-1; 86     } 87     return up+1; 88 } 89 int main(){ 90     int maxn; 91     while(~scanf("%d%d%d",&knum,&c,&m)){ 92         sx=0;se=knum+c+1; 93         maxn=0; 94         for(int i=1;i<=knum+c;i++) 95           for(int j=1;j<=knum+c;j++){ 96                scanf("%d",&map[i][j]); 97                if(map[i][j]==0) 98                   map[i][j]=INF; 99           }100              Floy();101           for(int i=1;i<=knum+c;i++)102             for(int j=1;j<=knum+c;j++)103                if(map[i][j]<INF&&map[i][j]>maxn)104                    maxn=map[i][j];105 106              printf("%d\n",dinic2(maxn));107 108         }109 }
View Code

 

Optimal Milking


联系
我们