題意：
? ? ?一個農(nóng)場主有一些奶牛，和一些機(jī)器，每臺機(jī)器有自己的服務(wù)上限，就是一天最多能給多少頭奶牛擠奶，給你任意兩點(diǎn)的距離，問你讓所有的奶牛都被擠奶時，奶牛于機(jī)器最遠(yuǎn)距離的最近是多少。

思路：

? ? ? 求最遠(yuǎn)的最近，二分，然后用最大流去判斷是否所有的奶牛都被擠奶了，簡單題目，不多解釋了，還有注意一點(diǎn)就是二分前記得Floyd一下，他沒說給的是最短距離。

#include<stdio.h> #include<string.h> #include<queue>#define N_node 250 #define N_edge 150000 #define INF 1000000000using namespace std;typedef struct {int to ,next ,cost; }STAR;typedef struct {int x ,t; }DEP;STAR E[N_edge]; DEP xin ,tou; int list[N_node] ,listt[N_node] ,tot; int deep[N_node] ,map[N_node][N_node];void add(int a ,int b ,int c) {E[++tot].to = b;E[tot].cost = c;E[tot].next = list[a];list[a] = tot;E[++tot].to = a;E[tot].cost = 0;E[tot].next = list[b];list[b] = tot; }int minn(int x ,int y) {return x < y ? x : y; }bool BFS_Deep(int s ,int t ,int n) {memset(deep ,255 ,sizeof(deep));xin.x = s ,xin.t = 0;deep[xin.x] = xin.t;queue<DEP>q;q.push(xin);while(!q.empty()){tou = q.front();q.pop();for(int k = list[tou.x] ;k ;k = E[k].next){xin.x = E[k].to;xin.t = tou.t + 1;if(deep[xin.x] != -1 || !E[k].cost)continue;deep[xin.x] = xin.t;q.push(xin);}}for(int i = 0 ;i <= n ;i ++)listt[i] = list[i];return deep[t] != -1; }int DFS_Flow(int s ,int t ,int flow) {if(s == t) return flow;int nowflow = 0;for(int k = listt[s] ;k ;k = E[k].next){int to = E[k].to ,c = E[k].cost;listt[s] = k;if(deep[to] != deep[s] + 1 || !E[k].cost)continue;int tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));nowflow += tmp;E[k].cost -= tmp;E[k^1].cost += tmp;if(nowflow == flow) break;}if(!nowflow) deep[s] = 0;return nowflow; }int DINIC(int s ,int t ,int n) {int ans = 0;while(BFS_Deep(s ,t ,n)){ans += DFS_Flow(s ,t ,INF);}return ans; }void Floyd(int n) {for(int k = 1 ;k <= n ;k ++)for(int i = 1 ;i <= n ;i ++)for(int j = 1 ;j <= n ;j ++)map[i][j] = minn(map[i][j] ,map[i][k] + map[k][j]); }bool ok(int mid ,int K ,int C ,int M) {memset(list ,0 ,sizeof(list));tot = 1;for(int i = 1 ;i <= K ;i ++)add(0 ,i ,M);for(int i = 1 ;i <= K ;i ++)for(int j = K + 1 ;j <= K + C ;j ++)if(mid >= map[i][j]) add(i ,j ,1);for(int i = 1 ;i <= C ;i ++)add(i + K ,K + C + 1 ,1);return DINIC(0 ,C + K + 1 ,C + K + 1) == C; }int main () {int K ,C ,M;int i ,j ,a;while(~scanf("%d %d %d" ,&K ,&C ,&M)){for(i = 1 ;i <= K + C ;i ++)for(j = 1 ;j <= K + C ;j ++){scanf("%d" ,&map[i][j]);if(!map[i][j]) map[i][j] = INF;}Floyd(K + C);int Max = 0;for(i = 1 ;i <= K ;i ++)for(j = K + 1 ;j <= K + C ;j ++)if(Max < map[i][j])Max = map[i][j];int low = 0 ,up = Max ,mid ,ans;while(low <= up){mid = (low + up) >> 1;if(ok(mid ,K ,C ,M)){up = mid - 1;ans = mid;}else low = mid + 1;}printf("%d\n" ,ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj2112 二分最大流+Floyd的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。