[SCOI2007][bzoj1070] 修車 [費用流]

題面

傳送門

思路

我們考慮某個勞工修車的從前到後序列如下：

${W_1,W_2,W_3,...,W_n}$

那麼，對于這n輛車的車主而言，他們等候的總時間為：

$\sum_{i=1}^{n}W_i\ast\left(n-i+1\right)=nW_1+\left(n-1\right)W_2+...+2W_{n-1}+W_n$

這一步很重要，因為經過這一步推導，我們發現：對于“把第i輛車讓第j個人在“需要消耗k次時間”的那個個位置修”這一個決策，可以等同為進行一個費用為$T\left(i,j\right)\ast k$的決策

是以我們可以得到一個決策集合：決策$\left(i,j,k\right)=T\left(i,j\right)\ast k$表示“把第i輛車讓第j個人在“需要消耗k次時間”的那個個位置修”

那實際上我們就是對于每個i選取一個這樣的決策，同時這個決策的$\left(j,k\right)$不能相同

那就好辦了，我們建立一個二分圖，左邊是n輛車，右邊是n*m個上述狀态的二進制組$\left(j,k\right)$（可以證明$k\leq n$）

源點向車連邊，而決策二進制組向彙點連邊，流量1費用0

中間的邊（注意這是一個完全二分圖）就是流量1費用$T\left(i,j\right)\ast k$的

跑最小費用最大流即可

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define inf 1e9
#define id(i,j) (i-1)*n+j
using namespace std;
inline int read(){
    int re=0,flag=1;char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re*flag;
}
int n,m,cnt=-1,ans,first[1010],dis[1010],vis[1010];
struct edge{
    int to,next,w,cap;
}a[100010];
inline void add(int u,int v,int w,int cap){
    a[++cnt]=(edge){v,first[u],w,cap};first[u]=cnt;
    a[++cnt]=(edge){u,first[v],-w,0};first[v]=cnt;
}
bool spfa(int s,int t){
    int q[5010],head=0,tail=1,u,v,w,i;
    memset(dis,-1,sizeof(dis));memset(vis,0,sizeof(vis));
    q[0]=t;vis[t]=1;dis[t]=0;
    while(head<tail){
        u=q[head++];vis[u]=0;
        for(i=first[u];~i;i=a[i].next){
            v=a[i].to;w=a[i].w;
            if(a[i^1].cap&&((dis[v]==-1)||(dis[v]>dis[u]-w))){
                dis[v]=dis[u]-w;
                if(!vis[v]) vis[v]=1,q[tail++]=v;
            }
        }
    }
    return ~dis[s];
}
int dfs(int u,int t,int limit){
    if(u==t||!limit){vis[u]=1;return limit;}
    int i,v,f,flow=0,w;vis[u]=1;
    for(i=first[u];~i;i=a[i].next){
        v=a[i].to;w=a[i].w;
        if(!vis[v]&&a[i].cap&&(dis[v]==dis[u]-w)){
            if(!(f=dfs(v,t,min(limit,a[i].cap)))) continue;
            a[i].cap-=f;a[i^1].cap+=f;
            ans+=f*w;flow+=f;limit-=f;
            if(!limit) return flow;
        }
    }
    return flow;
}
int zkw(int s,int t){//zkw費用流
    int re=0;
    while(spfa(s,t)){
        vis[t]=1;
        while(vis[t]){
            memset(vis,0,sizeof(vis));
            re+=dfs(s,t,inf);
        }
    }
    return re;
}
int main(){
    memset(first,-1,sizeof(first));int i,j,k,t1;
    m=read();n=read();
    for(i=1;i<=n;i++) add(0,i,0,1);
    for(i=1;i<=m;i++) for(j=1;j<=n;j++) add(n+id(i,j),n+n*m+1,0,1);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            t1=read();
            for(k=1;k<=n;k++){
                add(i,n+id(j,k),t1*k,1);
            }
        }
    }
    zkw(0,n+n*m+1);
    printf("%.2lf",((double)ans)/((double)n));//注意輸出保留兩位小數
}                

轉載于:https://www.cnblogs.com/dedicatus545/p/8733196.html