【Codeforces 1187G】Gang Up | Mrsrz's blog

分层图费用流。

题目大意：

给定一张 $n$ 个点 $m$ 条边的无向连通图，有 $k$ 个人分别从一些点，想走到 $1$ 号点。

走 $1$ 条边要 $1$ 个时刻，一个时刻可以走 $1$ 条边也可以不走。

一个人如果 $t$ 时刻才到 $1$ 号点，要花费 $c\cdot t$ 的代价。

一条边一个方向上某一时刻如果有 $a$ 个人同时经过，要花费 $d\cdot a^2$ 的代价。

$c$ 和 $d$ 都是给定常数。

求最小代价。

题解：

按照走过的边数，建原图的分层图。

对每个时刻的每个点，向下一时刻的同一个点连边，表示不走。

然后 $d\cdot a^2$，将 $a^2$ 拆成 $1+3+5+7+\cdots$ 也是常规操作。

最多一共会有 $(n+k)$ 个时刻，需要建 $n(n+k)+2$ 个点。

对于一条边，拆成 $2k(n+k)$ 条边。

然后跑费用流即可。

这里要注意加边时尽可能把价值小的边放前面，这样费用流常数比较小，否则可能被卡常。

Code：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=6000,inf=1e9;
struct edge{
    int to,nxt,cap,cost;
}e[(int)1e7];
int n,cnt=1,head[N],T,iter[N],m,k,c,d,a[N],TT[55][120],nod;
int dist[N],ans;
bool vis[N];
int q[1234567]; 
inline void addedge(int u,int v,int cost,int cap){
    e[++cnt]=(edge){v,head[u],cap,cost},head[u]=cnt;
    e[++cnt]=(edge){u,head[v],0,-cost},head[v]=cnt;
}
int dfs(int u,int f){
    if(u==T||!f)return f;
    vis[u]=1;
    int ret=0;
    for(int&i=iter[u];i;i=e[i].nxt)
    if(e[i].cap&&!vis[e[i].to]&&dist[e[i].to]==dist[u]+e[i].cost){
        int d=dfs(e[i].to,min(f,e[i].cap));
        e[i].cap-=d,e[i^1].cap+=d,f-=d,ret+=d;
        if(!f)break;
    }
    vis[u]=0;
    return ret;
}
bool MCMF(){
    for(int i=1;i<=T;++i)dist[i]=1e9+1;
    int h=1,t=1;q[1]=0;
    for(;h<=t;){
        int u=q[h++];
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
        if(e[i].cap&&dist[e[i].to]>dist[u]+e[i].cost){
            dist[e[i].to]=dist[u]+e[i].cost;
            if(!vis[e[i].to])
            vis[e[i].to]=1,q[++t]=e[i].to;
        }
    }
    if(dist[T]>=1e9)return 0;
    memcpy(iter,head,sizeof(int)*(T+2));
    while(int f=dfs(0,inf))ans+=dist[T]*f;
    return 1;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k>>c>>d;
    for(int i=1;i<=n;++i)
    for(int t=0;t<=101;++t)TT[i][t]=++nod;
    T=nod+5;
    for(int i=1;i<=k;++i)cin>>a[i],addedge(0,TT[a[i]][0],0,1);
    for(int t=1;t<=101;++t){
        for(int i=1;i<=n;++i)addedge(TT[i][t-1],TT[i][t],c,k);
    }
    while(m--){
        int u,v;
        cin>>u>>v;
        for(int t=0;t<101;++t)
        for(int i=1;i<=k;++i)addedge(TT[u][t],TT[v][t+1],c+d*(i*i-(i-1)*(i-1)),1),addedge(TT[v][t],TT[u][t+1],c+d*(i*i-(i-1)*(i-1)),1);
    }
    for(int t=0;t<=101;++t)addedge(TT[1][t],T,0,k);
    while(MCMF());
    cout<<ans<<'\n';
    return 0;
}