ProblemG

CrimeWave – The Sequel

Input: StandardInput

Output: StandardOutput

TimeLimit: 2 Seconds

n bankshave been robbed this fine day. m (greater than orequal to n) police cruisers are on duty at variouslocations in the city. n of the cruisers should bedispatched, one to each of the banks, so as to minimize the averagetime of arrival at the n banks.

Input

Theinput file contains several sets of inputs. The description of eachset is given below:

Thefirst line of input contains 0 < n <= m <=20. n lines follow, each containing m positivereal numbers: the travel time for cruiser m to reachbank n.

Inputis terminated by a case where m=n=0. This case should notbe processed.

Output

Foreach set of input output a single number: the minimum average traveltime, accurate to 2 fractional digits.

SampleInput Outputfor 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

13.33

Problemsetter: GordonCormack, EPS

题意：

有m个警察，派n个警察到n个银行，给出每个警察到各银行的时间，求最小的平均时间。

分析：

平均乘上n就是总时间，也就是要最小化总时间，那么用费用流就可以解决问题。各银行向每个警察连边，容量1,费用为时间;增加源点，源点向各银行连边，容量1,费用0;增加汇点，警察向汇点连边，容量1,费用0。在图中跑费用流就行。

这题最恶心的地方在于保留小数，结果加上eps再输出。这里涉及到保留小数方法，是用传统的四舍五入还是用银行家舍入？都不知道以后涉及到小数的输出要怎么搞了，这种东西就该spj啊。

/*
 *
 *	Author	:	fcbruce
 *
 *	Date	:	2014-09-05 20:37:26 
 *
 */
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include
                 #include 
                 
                   #define sqr(x) ((x)*(x)) #define LL long long #define itn int #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 #define eps 1e-10 #ifdef _WIN32 #define lld %I64d #else #define lld %lld #endif #define maxm 2333 #define maxn 64 using namespace std; int fir[maxn]; int u[maxm],v[maxm],cap[maxm],flow[maxm],nex[maxm]; double cost[maxm]; int e_max; double d[maxn]; int p[maxn]; bool inq[maxn]; int q[maxm<<3]; inline void add_edge(int _u,int _v,int _cap,double _cost) { int e; e=e_max++; u[e]=_u;v[e]=_v;cap[e]=_cap;cost[e]=_cost; nex[e]=fir[u[e]];fir[u[e]]=e; e=e_max++; u[e]=_v;v[e]=_u;cap[e]=0;cost[e]=-_cost; nex[e]=fir[u[e]];fir[u[e]]=e; } void SPFA(int s) { memset(inq,0,sizeof inq); memset(d,0x7f,sizeof d); int f,r; d[s]=0; q[f=r=0]=s; while (f<=r) { int x=q[f++]; inq[x]=false; for (int e=fir[x];~e;e=nex[e]) { if (cap[e]>flow[e] && d[v[e]]>d[u[e]]+cost[e]+eps) { d[v[e]]=d[u[e]]+cost[e]; p[v[e]]=e; if (!inq[v[e]]) { inq[v[e]]=true; q[++r]=v[e]; } } } } } pair
                  
                    min_cost_flow(int s,int t) { memset(flow,0,sizeof flow); double total_cost=0; int total_flow=0; for (;;) { SPFA(s); if (d[t]>INF) break; int _f=INF; for (int e=p[t];;e=p[u[e]]) { _f=min(_f,cap[e]-flow[e]); if (u[e]==s) break; } for (int e=p[t];;e=p[u[e]]) { flow[e]+=_f; flow[e^1]-=_f; if (u[e]==s) break; } total_cost+=d[t]*_f; total_flow+=_f; } return make_pair(total_cost,total_flow); } int main() { #ifdef FCBRUCE freopen(/home/fcbruce/code/t,r,stdin); #endif // FCBRUCE int n,m; while (scanf( %d%d,&n,&m),n||m) { int s=0,t=n+m+1; e_max=0; memset(fir,-1,sizeof fir); double w; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { scanf( %lf,&w); add_edge(i,n+j,1,w); } } for (int i=1;i<=n;i++) add_edge(s,i,1,0); for (int j=1;j<=m;j++) add_edge(j+n,t,1,0); auto res=min_cost_flow(s,t); printf( %.2f ,res.first/res.second+eps); } return 0; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：UVALive 4885 Task 差分约束	下一篇：uva 1385 - Billing Tables(字典..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: