uva 10746 - Crime Wave – The Sequel

Problem G

Crime Wave – The Sequel

Input: Standard Input

Output: Standard Output

Time Limit: 2 Seconds

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 nbanks.

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                             Output for 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

13.33

---

Problemsetter: Gordon Cormack, EPS

二分圖最大匹配轉最小費用流 - 加上源點與匯點
注意浮點數誤差，加上epsilon(1e-8)以保證四捨五入

#include<stdio.h>
#include<cstring>
#include<queue>
#include<cmath>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i,n) REP(i, 0, n)
#define DBG 0
#define INF (1e30)
#define MAXN 50
#define MAXM 900
#define eps 1e-8
using namespace std;

int N,M,D,K,LD,cases=1,e=0;
int head[MAXM],v[MAXM],next[MAXM],cap[MAXM],
    cnt[MAXN],flow[MAXN],p[MAXN],pe[MAXN];
double RES,dis[MAXN],cost[MAXM];
bool trav[MAXN];

void addedge(int a,int b,int K,double w){
    if(DBG)printf("addedge(%d): %d %d\n",e,a,b);
    v[e]=b,cap[e]=K,cost[e]=w,
    next[e]=head[a],head[a]=e++;
    v[e]=a,cap[e]=0,cost[e]=-w,
    next[e]=head[b],head[b]=e++;
}
bool relax(int u,int v,int e){
    if(DBG)printf("enter relax(%d) u v cap cost dis[v] %d %d %d %f %f\n",e,u,v,cap[e],cost[e],dis[v]);
    if(cap[e]&&dis[u]+cost[e]<dis[v]){
        flow[v]=min(flow[u],cap[e]);
        dis[v]=dis[u]+cost[e];
        p[v]=u,pe[v]=e;
        if(DBG)printf("  relax(%d): v cap dis %d %d %f\n",e,v,cap[v],dis[v]);
        return 1;
    }
    return 0;
}
void SPFA(int s,int t){
    int i,b,c,d,f;
    double w;
    queue<int>q;
    rep(i,M+N+2)dis[i]=INF;
    memset(trav,0,sizeof(trav));
    memset(flow,0,sizeof(flow));
    flow[0]=LD,dis[0]=0;
    q.push(0);
    while(q.size()){
        c=q.front(),w=dis[c];q.pop();
        if(DBG)printf("spfa v flow dis %d %d %f\n",c,flow[c],dis[c]);
        trav[c]=0;
        for(i=head[c];i!=-1;i=next[i]){
            b=v[i];
            if(relax(c,b,i)&&!trav[b]){
                if(DBG)printf("b %d F %d\n",b,cap[i]);
                trav[b]=1;
                q.push(b);
            }
        }
    }
    f=flow[t];
    LD-=f,RES+=f*dis[t];
    if(DBG)printf("final LD cost dis: %d %d %f\n",LD,f,dis[t]);
    for(b=t;b!=s;b=p[b]){if(DBG)printf("cut %d\n",pe[b]);cap[pe[b]]-=f,cap[pe[b]^1]+=f;}
}
void edmond(int s,int t){
    while(LD){
        if(DBG)printf("edm\n");
        SPFA(s,t);
    }
    if(DBG)printf("dist: %d\n",RES);
}
void ans(){
    RES=0,LD=N;
    edmond(0,N+M+1);
    printf("%.2f\n",RES/N+eps);
}
int main(){
    int a,b,cases=1;
    double c;
    while(scanf("%d%d",&N,&M)==2){
        if(N==0&&M==0)break;
        if(DBG)printf("N M %d %d\n",N,M);
        memset(head, -1, sizeof(head)),e=0;
        rep(i,N){
            rep(j,M)scanf("%lf",&c),addedge(j+1,i+M+1,1,c);
        }
        rep(i,N)addedge(i+M+1,N+M+1,1,0);
        rep(i,M)addedge(0,i+1,1,0);
        if(DBG)printf("cases %d\n",cases++);
        ans();
    }
}