題目描述:
農場主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<