程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj2112Optimal Milking(最優秀的擠奶方案)——floyd+最大流+二分

poj2112Optimal Milking(最優秀的擠奶方案)——floyd+最大流+二分

編輯:關於C++

 

題目描述:
農場主John 將他的K(1≤K≤30)個擠奶器運到牧場,在那裡有C(1≤C≤200)頭奶牛,在奶
牛和擠奶器之間有一組不同長度的路。K個擠奶器的位置用1~K的編號標明,奶牛的位置用K+1~
K+C 的編號標明。
每台擠奶器每天最多能為M(1≤M≤15)頭奶牛擠奶。
編寫程序,尋找一個方案,安排每頭奶牛到某個擠奶器擠奶,並使得C 頭奶牛需要走的所有
路程中的最大路程最小。每個測試數據中至少有一個安排方案。每條奶牛到擠奶器有多條路。

輸入描述:
測試數據的格式如下:
第1 行為3 個整數K、C 和M。
第2~K+C+1 行,每行有K+C 個整數,描述了奶牛和擠奶器(二者合稱實體)之間的位置,
這K+C 行構成了一個沿對角線對稱的矩陣。第2 行描述了第1 個擠奶器離其他實體的距離,…,
第K+1 行描述了第K 個擠奶器離其他實體的距離;第K+2 行描述了第1 頭奶牛離其他實體的距
離,…。這些距離為不超過200 的正數。實體之間如果沒有直接路徑相連,則距離為0。實體與
本身的距離(即對角線上的整數)也為0。

輸出描述:
輸出一個整數,為所有方案中,C 頭奶牛需要走的最大距離的最小值。

這裡寫圖片描述

因為題目要求路徑裡面最大的最小,所以先用floyd求得任意兩點之間的最短路,然後二分枚舉可能的最大邊,根據所枚舉的最大邊的前提限制,建圖,源點到各個奶牛的容量為1,各個牛奶站到匯點的容量為M,如果某個奶牛到奶牛站的距離小於等於所枚舉的最大邊,則容量為1,求得最大流是否等於C

#include
#include
#include
#include
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i,a,b) for(int i=(a);i<=(b);++i)
const int maxn=250;
const int INF=1<<30;
using namespace std;
int n,s,t;
int K,C,M;
struct Edge{
    int from,to,cap,flow;
    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
vector edges;
vector G[maxn];
int gap[maxn],d[maxn],cur[maxn],p[maxn];
inline void addedge(int u,int v,int c){
    edges.push_back(Edge(u,v,c,0));
    edges.push_back(Edge(v,u,0,0));
    int m=edges.size();
    G[u].push_back(m-2);
    G[v].push_back(m-1);
}
int ISAP(){
    s=0,t=n;
    memset(cur,0,sizeof(cur));
    memset(d,0,sizeof(d));
    memset(gap,0,sizeof(gap));
    int x=s,flow=0,a=INF;
    while(d[s]e.flow&&d[e.to]+1==d[x]){
                p[e.to]=G[x][i];
                cur[x]=i;
                x=e.to;
                ok=1;
                a=min(a,e.cap-e.flow);
                break;
            }
        }
        if(!ok){
            int m=n;
            for(int i=0;ie.flow) m=min(m,d[e.to]);
            }
            if(--gap[d[x]]==0) break;
            gap[d[x]=m+1]++;
            cur[x]=0;
            if(x!=s) x=edges[p[x]].from;
        }
    }
    return flow;
}



int g[maxn][maxn];
int maxh,maxedge;
void floyd(){
    maxh=-1;
    FORD(k,1,n)FORD(i,1,n){
        if(g[i][k]>K>>C>>M;
    n=K+C;
    FORD(i,1,n)FORD(j,1,n){
        scanf(%d,&g[i][j]);
        if(g[i][j]==0) g[i][j]=INF;
    }
    floyd();
    n+=2;
    int maxflow;
    int l=0,r=maxh;
    while(l>1;
        build(mid);
        maxflow=ISAP();
        cout<=C) r=mid;
        else l=mid+1;
    }
    build(r);
    cout<
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved