BZOJ 1070 修车-神奇网络流

传送门
题意：中文题。

Solution：
因为这道题每个工人可以维修多个汽车，所以说没法直接用费用流，我们先想一个简单的贪心思路：假如说我们考虑一个工人的情况，那么他修车所需的时间为：

t 1 + (t 1 + t 2) + (t 1 + t 2 + t 3) + \dots + (t 1 + \dots + t n)

变形一下该式：

n * t 1 + (n - 1) * t 2 + \dots + t n

容易看出，我们修车的顺序一定是从耗时小的开始，看到数据范围是50，所以说我们可以试试拆点：一个工人的维修情况可以看成多个只能维修一辆车的工人的维修情况，只不过他们各自需要1-N倍的时间，经过这次拆点，我们就可以把问题转化成普通的费用流了。
这道题的建图非常巧妙，同时也交给我们一个技巧：当数据很小的时候，可以考虑多拆点。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=70;
int n,m,S,T;
int g[N][N];
int size=1;
struct edg{
    int to,next,flow,v;
}e[3*N*N*N];
int x,y,f,v;
int dis[N*N];
int q[2*N*N*N];
int pre[N*N],prv[N*N];
bool vis[N*N];
int ansf,ansv;
int head[N*N];
int tt;
void add(int x,int y,int f,int v)
{
    size++;
    e[size].to=y;
    e[size].flow=f;
    e[size].v=v;
    e[size].next=head[x];
    head[x]=size;
}
bool SPFA()
{
    for (int i=0;i<=T;i++)
        vis[i]=0,dis[i]=1e9;
    int h=0,t=0;
    int x,y;
    q[++t]=S;vis[S]=1;dis[S]=0;
    while (h<t)
    {
        x=q[++h];vis[x]=0;
        for (int i=head[x];i;i=e[i].next)
        {
            y=e[i].to;
            if (e[i].flow&&dis[y]>dis[x]+e[i].v)
            {
                dis[y]=dis[x]+e[i].v;
                pre[y]=x;
                prv[y]=i;
                if (!vis[y])
                {
                    q[++t]=y;
                    vis[y]=1;
                }
            }
        }
    }
    return (dis[T]!=1e9);
}
int main()
{
    //scanf("%d",&tt);
    tt=1;
    while (tt--)
    {
        size=1;
        memset(e,0,sizeof(e));
        memset(head,0,sizeof(head));
        scanf("%d%d",&m,&n);
        S=0;T=n*m+n+1;
        for (int j=1;j<=n;j++)
        {
            add(S,j,1,0);
            add(j,S,0,0);
            for (int i=1;i<=m;i++)
            {
                scanf("%d",&g[j][i]);
                for (int k=1;k<=n;k++)//枚举第几个 
                {
                    add(j,i*n+k,1,k*g[j][i]);
                    add(i*n+k,j,0,-k*g[j][i]);
                }
                add(i*n+j,T,1,0);
                add(T,i*n+j,0,0);
            }
        }
        ansv=0,ansf=0;
        while (SPFA())
        {
            int F=1e9;
            for (int i=T;i!=S;i=pre[i])
                F=min(F,e[prv[i]].flow);
            ansv+=F*dis[T];
            ansf+=F;
            for (int i=T;i!=S;i=pre[i])
                e[prv[i]].flow-=F,e[prv[i]^1].flow+=F;
        }
        printf("%.2f\n",1.0*ansv/n);
    }
}