题解 P2053 【[SCOI2007]修车】

· · 题解

前言：

本蒟蒻觉得这道题出的不错，一开始我只想到了二分答案，根本没有想到如何构造网络流，看了题解后才大概理解的。

思路：

假设我们现在只有一个修车师傅，共有A1,A2...An这n辆车，那么所有人的等待时间就分别为:

**那所有人的等待时间呢？** 加起来，我们发现所有人的等待时间应该是: $A1*n+A2*(n-1)+...+An

那我们对每辆车被等待的时间考虑，发现越后修的被等待的时间越少

而且显而易见的，所有车被等待的时间即为所有人等待的时间

做法：

那我们从每辆车被等待的时间思考，思路也不是很难了，

将M位师傅拆成N*M个点，第(i-1)*N+j个点表示的是在修第j辆车的第i位师傅，并将这个点连向每辆车，容量为1，边权为Cki*j（Cij为第i辆车被第j位师傅修所花的时间,1<=k<=N），

然后再源点朝M个车点建边，N*M个师傅点朝汇点建边，都是边权为0，容量为1的边，最后跑最小费用最大流就行了。

同时建反向边应该不用我赘述了吧

注：本来是先修被等的时间越多，但是反过来仔细想先也没有什么问题

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#define N 2010
#define K 210
#define M 100010
#define inf 0x7fffffff/2
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
    char ch=getchar();
    ll s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
struct edge
{
    int next,to,fl,v;
}e[M<<1];
int head[N],cnt=1;
int n,m;
int dist[N],pre[N],wch[N];
//pre表示spfa中每个点是从哪条边来的,wch表示spfa中每个点是从哪个点来的
queue<int>Q;
int vis[N];
int c[K][K];//第i辆车被第j格师傅修所花的时间
int s,t;
int minn[N];//minn表示spfa中s到每个点所经过的边中的最小流量
inline void add_edge(int from,int to,int fl,int v)
{
    e[++cnt].to=to;
    e[cnt].next=head[from];
    e[cnt].v=v;
    e[cnt].fl=fl;
    head[from]=cnt;
}//加边
void dfs(int now,int sub)
{
    e[wch[now]].fl-=sub;
    e[wch[now]^1].fl+=sub;
    if(pre[now])dfs(pre[now],sub);
}//修改流量
inline int spfa()
{
    for(register int i=1;i<=t;i++)dist[i]=inf;
    memset(vis,0,sizeof(vis));while(!Q.empty())Q.pop();
    Q.push(s),vis[s]=1;minn[s]=inf;//不要忘了给minn[s]设初值
    while(!Q.empty())
    {
        int x=Q.front();Q.pop();vis[x]=0;
        for(register int i=head[x];i;i=e[i].next)
        {
            if(dist[e[i].to]>dist[x]+e[i].v&&e[i].fl>0)
            {
                dist[e[i].to]=dist[x]+e[i].v;
                wch[e[i].to]=i;pre[e[i].to]=x;
                minn[e[i].to]=min(minn[x],e[i].fl);
                if(!vis[e[i].to])
                {
                    Q.push(e[i].to);
                    vis[e[i].to]=1;
                }
            }
        }
    }
    if(dist[t]==inf)return inf;//如果从s到不了t了
    dfs(t,minn[t]);//修改边的流量
    return minn[t]*dist[t];
}//最短路
inline int EK()
{
    int sum=0;
    while(1)
    {
        int x=spfa();
        if(x==inf)return sum;//没有增广路了
        else sum+=x;
    }
}
int main()
{
    m=read(),n=read();
    t=n*m+n+1;
    for(register int i=1;i<=n;i++)
    {
        for(register int j=1;j<=m;j++){c[i][j]=read();}
    }
    for(register int i=1;i<=n*m;i++)
    {
        add_edge(s,i,1,0);add_edge(i,s,0,0);
    }
    for(register int i=1;i<=m;i++)
    {
        for(register int j=1;j<=n;j++)
        {
            for(register int k=1;k<=n;k++)
            {
                int now=(i-1)*n+k;
                add_edge(now,j+n*m,1,c[j][i]*k);
                add_edge(j+n*m,now,0,-c[j][i]*k);
            }
        }
    }
    for(register int i=1;i<=n;i++)add_edge(n*m+i,t,1,0),add_edge(t,n*m+i,0,0);
    printf("%.2lf",double(double(EK())/double(n)));
    return 0;
    //我的建图方式可能和前面我的题解写的方式不大一样，代码中我是师傅练得源点，车连的汇点
}

后记：

希望大家在A了这道题后可以看看NOI2012的美食节，这道题在本题模型的基础上提出了更多的思考和优化，其中那道题的优化很有意思，主要了运用了spfa在稀疏图中速度更快的理论知识，值得一做。