题解【CF1187G Gang Up】

传送门。

$\texttt{Description}$

$k$ 个人位于一张无向图上，每个时间可以选择走动或停留。

有 $a$ 个人同时经过一条边需要 $d\times a^2$ 的代价。

一个人到达 $1$ 的时间为 $t$，则需要话费 $c\times t$ 的代价。

求所有人到达 $1$ 后的最小代价。

$1\le n,m,k\le 50$。

$\texttt{Solution}$

发现题目中涉及到了时间，直接想到按照时间分层。

第 $i$ 个点，在第 $j$ 个时间的编号为 $i+j\times n$。

我们用 $(i,j)$ 表示第 $i$ 个点第 $j$ 个时间的状态。

一开始对于每一个 $a_i$，从 $s$ 向 $(a_i,0)$ 连一条容量为 $1$，费用为 $0$ 的边，这是很显然的。

每一个人都可以选择停留，所以将 $(i,j)$ 向 $(i,j+1)$ 连一条容量为 $\infty$，费用为 $c$。特别的，若 $i=1$，则费用为 $0$，因为已经到了 $1$ 号点，任务就结束了。

但是你会发现 $d^2$ 这个条件特别不好处理。

但是你会把 $d^2$ 转化成 $\sum_{i=1}^d(2\times d-1)$ 的形式，所以就可以根据这道题的 $\texttt{trick}$，从对于原图的一条 $u$ 到 $v$ 的边，对于每一层，连 $k$ 条边，但不同的是，对于第 $t$ 条边，容量为 $1$，费用为 $d\times (2t-1)+c$。

这个怎么解释呢，容量一定的情况下，我们肯定会从最小的费用的那条边到尽可能流的最大费用的这些边流满，这些边求和肯定就是 $d^2a$ 了。其中 $a$ 为我们的流量。

然后就做完了，数组不要开小，代码：

int main()
{
    n=read(),m=read(),k=read(),c=read(),D=read();
    int s=0;
    for(register int i=1;i<=k;i++)
    {
        int x=read();
        add_edge(s,x,1,0);
    }
    for(register int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        for(register int j=1;j<=n+k;j++)
            for(register int kk=1;kk<=k;kk++)
                add_edge(u+(j-1)*n,v+j*n,1,D*((kk<<1)-1)+c),add_edge(v+(j-1)*n,u+j*n,1,D*((kk<<1)-1)+c);;
    }
    for(register int i=1;i)
    {
        for(register int j=2;j<=n;j++)
            add_edge(j+(i-1)*n,j+i*n,INF,c);
        add_edge(1+(i-1)*n,1+i*n,INF,0);
    }
    t=1+(k+n-1)*n;
    MCMF();
    return 0;
}

$$\texttt{The End.by UF}$$