原題： n banks have been robbed this fine day. m (greater than or equal to n) police cruisers are on duty at various locations in the city. n of the cruisers should be dispatched, one to each of the banks, so as to minimize the average time of arrival at the n banks. Input The input file contains several sets of inputs. The description of each set is given below: The first line of input contains 0 < n ≤ m ≤ 20. n lines follow, each containing m positive real numbers: the travel time for cruiser m to reach bank n. Input is terminated by a case where m = n = 0. This case should not be PRocessed. Output For each set of input output a single number: the minimum average travel time, accurate to 2 fractional digits. Sample Input 3 4 10.0 23.0 30.0 40.0 5.0 20.0 10.0 60.0 18.0 20.0 20.0 30.0 0 0 Sample Output 13.33
中文： 有n個銀行被搶劫，有m個警察。給你每個警察到這n銀行的時間，現在問你每個銀行派一個警察，使得使得總消耗時間的平均和最小是多少？
#include<bits/stdc++.h>using namespace std;const int maxn=101;const double inf=100000000.000;const double eps = 1e-6;struct Edge//邊{ int from,to,cap,flow;//出點，入點，容量，當前流量，費用（也就是權值） double cost; Edge(int u,int v,int c,int f,double w):from(u),to(v),cap(c),flow(f),cost(w){}};struct MCMF{ int n,m; vector<Edge> edges;//保存表 vector<int> G[maxn];//保存鄰接關系 int inq[maxn];//判斷一個點是否在隊列當中（SPFA算法當中要用） double d[maxn];//起點到d[i]的最短路徑保存值 int p[maxn];//用來記錄路徑，保存上一條弧 int a[maxn];//找到增廣路徑后的改進量 void init(int n)//初始化 { this->n=n; for(int i=0;i<=n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap,double cost)//添加邊 { edges.push_back(Edge(from,to,cap,0,cost));//正向 edges.push_back(Edge(to,from,0,0,-cost));//反向 m=edges.size(); G[from].push_back(m-2);//按照邊的編號保存鄰接關系 G[to].push_back(m-1); } bool BellmanFord(int s,int t,int& flow,double& cost)//最短路徑算法 { for(int i=0;i<=n;i++) d[i]=inf*1.0; memset(inq,0,sizeof(inq)); d[s]=0; inq[s]=1; p[s]=0; a[s]=inf; queue<int> Q; Q.push(s); while(!Q.empty()) { int u=Q.front(); Q.pop(); inq[u]=0; for(int i=0;i<G[u].size();i++) { Edge& e=edges[G[u][i]]; if(e.cap>e.flow&&d[e.to]>d[u]+e.cost+eps)//尋找滿足容量大于流量的可松弛邊 { d[e.to]=d[u]+e.cost; p[e.to]=G[u][i]; a[e.to]=min(a[u],e.cap-e.flow); if(!inq[e.to])//是否在隊列當中 { Q.push(e.to); inq[e.to]=1; } } } } if(d[t]>=inf)//如果d[t]沒有被更新，相當于沒找到增廣路徑，則沒有最大流也沒有最小費用 return false; flow+=a[t];//更新最大流 cost+=(double )d[t]*(double)a[t];//單位流量乘以單位路徑長度用來計算消耗 for(int u=t;u!=s;u=edges[p[u]].from)//通過使用p[]保存的上一個邊的值來對剛剛找到的增廣路徑上面的流量進行更新 { edges[p[u]].flow+=a[t];//正向變更新 edges[p[u]^1].flow-=a[t];//反向變更新（用位運算實現的） } return true; } int MincostMaxflow(int s,int t,double& cost)//計算從s到t的最小消耗cost，返回最大流 { int flow = 0; cost=0; while(BellmanFord(s,t,flow,cost));//不斷尋找最短增廣路徑，直到找不到為止 return flow; }};MCMF mcmf;double tmp[21][21];int main(){ int n,m; ios::sync_with_stdio(false); while(cin>>n>>m,n+m) { mcmf.init(100); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>tmp[i][j]; } } mcmf.AddEdge(0,1,n,0); for(int i=1;i<=m;i++) mcmf.AddEdge(1,i+1,1,0); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) mcmf.AddEdge(1+i,1+m+j,1,tmp[j][i]); for(int i=1;i<=n;i++) mcmf.AddEdge(m+1+i,m+n+2,1,0); double ans; mcmf.MincostMaxflow(0,m+n+2,ans); cout<<fixed<<setprecision(2)<<(ans/n+eps)<<endl; } return 0;}思路： 裸的最小費用最大流問題，給每個警察到每個銀行建立一條邊，容量都是1，費用用給定的時間表示。 設置超級源點s’到源點s，容量設置成銀行的數量，用來控制出警的數量，然后把s點和所有警察連接上，容量設置為1，費用設置為0，最后把所有銀行連接到一個匯點上，每個邊的容量都是1，費用都設置為0即可。
此題是小數，所以一定要注意精度轉換！用eps最小精度來調節尋找最短增光路的松弛過程！結果也要加上eps
新聞熱點
疑難解答
