LG2053/BZOJ1070 「SCOI2007」修车 费用流

问题描述

LG2053

BZOJ1070

---

题解

将\(m\)个修理工拆为\(n \times m\)个，将修理工和车辆看做二分图，连出一个完全二分图。

边流量为\(1\)，费用为时间，费用流即可。

---

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-'){
        fh=-1;ch=getchar();
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

const int maxn=63;
const int maxm=13;
const int INF=0x3f3f3f3f;

int n,m;
int a[maxn][maxm];

int Head[100000],Next[1000000],to[1000000],tot=1,w[1000000],co[1000000];
int S,T;

void add(int a,int b,int c,int d){
    to[++tot]=b,Next[tot]=Head[a],Head[a]=tot,w[tot]=c,co[tot]=d;
}

bool vis[100000];
int now[1000000],pre[1000000];
int dis[100000];
int ans,flow;

bool spfa() {
    memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));
    queue<int>q;q.push(S);vis[S]=1;dis[S]=0;now[S]=INF;
    while(!q.empty()){
        int x=q.front();q.pop();vis[x]=0;
        for (int i=Head[x];i;i=Next[i]){
            int y=to[i],z=w[i],ww=co[i];
            if (!z||dis[y]<=dis[x]+ww) continue;
            dis[y]=dis[x]+ww;
            now[y]=min(now[x],z);
            pre[y]=i;
            if(!vis[y]){
                q.push(y);
                vis[y] = 1;
            }
        }
    }
    return dis[T]!=INF;
}

void upd(){
    flow+=now[T],ans+=dis[T]*now[T];
    int p=T;
    while(p!=S){
        int k=pre[p];
        w[k]-=now[T],w[k xor 1]+=now[T];
        p=to[k xor 1];
    }
}

int main(){
    read(m);read(n);tot=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            read(a[i][j]);
        }
    }
    S=n*(m+1)+1,T=S+1;
    for(int i=1;i<=n*m;i++){
        add(S,i,1,0);add(i,S,0,0);
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                int p=(i-1)*n+k;
                add(p,j+n*m,1,a[j][i]*k);add(j+n*m,p,0,-a[j][i]*k);
            }
        }
    }
    for(int i=1;i<=n;i++){
        add(n*m+i,T,1,0);add(T,n*m+i,0,0);
    }
    while(spfa())
        upd();
    double ret=(double)ans/(double)n*1.0;
    cout<<fixed<<setprecision(2)<<ret<<endl;
    return 0;
}