POJ 2112 Floyd + 二分 + 构图 + 最大流

题目大意：

　　给定K个处理站标号1……K，C头牛编号K+1……K+C，每个处理站最多处理M头牛产的牛奶，处理站和牛之间或者牛与牛之间都有一个距离，牛可以通过相邻边到达处理站或者通过其他牛的所在地到达指定的处理站，问如果合理分配，牛与指定处理站之间的最远距离是多少，保证至少有一种分配。

分析：

　　首先对于给定的图，需要用Floyd求出所有点之间的最短路（我在求最短路的时候脑残了一下，map[i][j]=0的话也就是没有边应该赋值为无穷大的！！！还有Floyd算法中最外层的循环一定是枚举的中间点！！！还有注意dis[][]相加的时候会产生数据越界的情况！！！慎重！！！）

　　然后二分枚举一个值mid，进行构图，建立一个超级源点ST，ST向1……K各连一条有向边，容量为M，建立一个超级汇点ED，K+1……K+C分别向ED连一条有向边，容量为1, 然后1……K和K+1……K+C之间如果最短距离dis[ i ][ j ] <= mid，也连一条有向边，容量为1,用Edmond_karp模版求出最大流flow与牛的头数C比较即可得到最终的答案，具体见代码。

代码：

poj2112

  1 /*2112    Accepted    920K    485MS    C++    2533B    2012-06-15 15:20:56*/
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <iostream>
  6 #include <algorithm>
  7 #include <vector>
  8 using namespace std;
  9 
 10 #define mpair make_pair
 11 #define pii pair<int,int>
 12 #define MM(a,b) memset(a,b,sizeof(a));
 13 typedef long long lld;
 14 typedef unsigned long long u64;
 15 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;}
 16 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;}
 17 #define maxn 240
 18 const int inf= 100000000; ///!!!!!!!
 19 
 20 int K,C,M;
 21 int map[maxn][maxn], dis[maxn][maxn];
 22 
 23 int ST,ED,NV;
 24 int g[maxn][maxn];
 25 
 26 void Floyd(){
 27     for(int i=1;i<ED;++i)
 28         for(int j=1;j<ED;++j)
 29             dis[i][j]= map[i][j];
 30 
 31     for(int k=1;k<ED;++k)
 32         for(int i=1;i<ED;++i)
 33             if( i!=k )
 34                 for(int j=1;j<ED;++j)
 35                     if( k!=j && i!=j )
 36                         up_min( dis[i][j], dis[i][k]+dis[k][j] );
 37 }
 38 
 39 bool vis[maxn];
 40 int pre[maxn], que[maxn];
 41 bool bfs(){
 42     MM( vis, 0 );
 43     int head= 0, tail= 0;
 44     que[tail++]= ST;
 45     vis[ST]= 1;
 46     while( head<tail ){
 47         int u= que[head++];
 48         for(int v=1;v<NV;++v){
 49             if( g[u][v]>0 && !vis[v] ){
 50                 pre[v]= u;
 51                 if( v==ED ) return 1;
 52                 que[tail++]= v;
 53                 vis[v]= 1;
 54             }
 55         }
 56     }
 57     return 0;
 58 }
 59 
 60 int Edmond_karp(int len){
 61     for(int i=0;i<NV;++i)
 62         for(int j=0;j<NV;++j)
 63             g[i][j]= 0;
 64     for(int i=1;i<=K;++i) g[ST][i]= M;
 65     for(int i=K+1;i<ED;++i) g[i][ED]= 1;
 66     for(int i=1;i<=K;++i)
 67         for(int j=K+1;j<ED;++j)
 68             g[i][j]= (dis[i][j]<=len);
 69 
 70     int ret= 0;
 71     while( bfs() ){
 72         int t= inf;
 73         for(int i=ED;i!=ST;i=pre[i])
 74             up_min( t, g[pre[i]][i] );
 75         ret+= t;
 76         for(int i=ED;i!=ST;i=pre[i]){
 77             g[pre[i]][i]-= t;
 78             g[i][pre[i]]+= t;
 79         }
 80     }
 81     return ret;
 82 }
 83 
 84 int solve(){
 85     int l= 1,r= 100000, mid;
 86     while( l<=r ){
 87         mid= (l+r)>>1;
 88         if( Edmond_karp(mid) == C ) r= mid-1;
 89         else l= mid+1;
 90     }
 91     return l;
 92 }
 93 
 94 int main()
 95 {
 96     //freopen("poj2112.in","r",stdin);
 97     while( cin>>K>>C>>M ){
 98         ST=0, ED= K+C+1, NV= K+C+2;
 99         for(int i=1;i<ED;++i){
100             for(int j=1;j<ED;++j){
101                 scanf("%d", &map[i][j]);
102                 if( map[i][j] == 0 ) map[i][j]= inf; /// !!!
103             }
104         }
105 
106         Floyd();
107         cout<< solve() <<endl;
108     }
109 }

一毛原创作品，转载请注明出处。