P2053 [SCOI2007]修车

题意

我们假设第\(i\)个工人修了\(j\)辆车，所用时间分别为\(t_1,t_2....t_j\)。

我们算一下他所用时间是多少：
\(t_1+(t_1+t_2)+(t_1+t_2+t_3)+...+(t_1+t_2+...+t_j)\)。
我们用费用提前计算的方法，可以写成：
\(t_1*j+t_2*(j-1)+...+t_j*1\)。

于是我们将每个工人拆成\(n\)个点，第\(i\)个点表示修第\(i\)辆车，现在我们就能处理费用了。

建图：
1.从\(S\)向每辆车连边，容量为1，费用为0。
2.从第\(i\)个点向第\(j\)个工人的\(n\)个点连边，向第\(k\ k\in[1,n]\)个点连容量为\(1\)，费用为\(k*t_{i,j}\)，\(t_{i,j}\)是第\(j\)个工人修\(i\)这辆车的时间。
3.从每个工人点向\(T\)连容量为\(1\)，费用为\(0\)的边。

跑最小费用最大流即可。

code:

#include<bits/stdc++.h>
using namespace std;
const int maxl=100010;
const int inf=1e9;
int n,m,cnt=1,S,T;
int head[maxl],dis[maxl];
bool vis[maxl];
struct edge{int to,nxt,flow,cost;}e[maxl<<1];
inline void add(int u,int v,int w,int c)
{
    e[++cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].to=v;
    e[cnt].flow=w;
    e[cnt].cost=c;
}
inline void addflow(int u,int v,int w,int c){add(u,v,w,c),add(v,u,0,-c);}
inline bool spfa()
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(S);dis[S]=0;vis[S]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();vis[x]=0;
        for(int i=head[x];i;i=e[i].nxt)
        {
            if(e[i].flow<=0)continue;
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].cost)
            {
                dis[y]=dis[x]+e[i].cost;
                if(!vis[y])q.push(y),vis[y]=1;
            }
        }
    }
    return dis[T]!=0x3f3f3f3f;
}
int dfs(int x,int lim)
{
    if(lim<=0||x==T)return lim;
    int res=lim;
    vis[x]=1;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(e[i].flow<=0||vis[y]||dis[y]!=dis[x]+e[i].cost)continue;
        int tmp=dfs(y,min(res,e[i].flow));
        res-=tmp;
        e[i].flow-=tmp,e[i^1].flow+=tmp;
        if(res<=0)break;
    }
    return lim-res;
}
inline int Dinic()
{
    int res=0,cost=0;
    while(spfa())
    {
        int flow=dfs(S,inf);
        res+=flow,cost+=dis[T]*flow;
    }
    return cost;
}
int main()
{
    scanf("%d%d",&m,&n);
    S=0,T=n*m+n+1;
    for(int i=1;i<=n;i++)addflow(S,i,1,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            addflow(j*n+i,T,1,0);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int x;scanf("%d",&x);
            for(int k=1;k<=n;k++)addflow(i,j*n+k,1,k*x);
        }
    printf("%.2lf",1.0*Dinic()/n);
    return 0;
}

P2053 [SCOI2007]修车

原文：https://www.cnblogs.com/nofind/p/12094770.html