CF1187G - Gang Up

题目大意

有$k$个人在一张无向图上往1走，可以选择在原地不动或者走一条边

一个人在$x$时间到达目的地的代价是$c\cdot x$，$c$是常数

一条边同一时间被$x$个人经过的代价是$x^2\cdot d$，$d$是常数

最小化代价


分析

无法贪心，无法最短路的题目，那就先试试网络流

考虑将时间和位置压在一起建立节点，时间$\leq n+k$

$(t,u)\rightarrow (t+1,u) $

$(t,u)\rightarrow (t+1,v)$

在原地保持的边代价为$c$，流量$\infty$

在两点间移动的代价由于与个数有关，可以建立$k$条边

每条代价是$d(i^2-(i-1)^2)+c=c+(2i-1)d$

得到一个$O((n+k)n)$点数$O((n+k)m\cdot k)$边数的图

然后可以考虑依次将每个人加入流量

但是实际上，并不需要显式地将所有边连出来跑网络流

每次加入一个点看做一个带回撤的最短路问题，有效的边只有$(n+k)m$条

因此复杂度为$O(k\cdot \text{SPFA}((n+k)n,(n+k)m))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
const int N=110,INF=1e9+10;

int n,m,k,C,D;
int a[N];
struct Edge{
	int to,nxt;
} e[N<<1];
int head[N],ecnt=1;
void AddEdge(int u,int v){
	e[++ecnt]=(Edge){v,head[u]};
	head[u]=ecnt;
}

int dis[N][N],pre[N][N],inq[N][N],G[N][N],W[N][N];
static queue <Pii> que;
void Upd(int x,int y,int d,int p){
	if(dis[x][y]>d) {
		dis[x][y]=d,pre[x][y]=p;
		if(!inq[x][y]) inq[x][y]=1,que.push(mp(x,y));
	}
}

int cnt[N][N];

int main(){
	n=rd(),m=rd(),k=rd(),C=rd(),D=rd();
	rep(i,1,k) a[i]=rd();
	rep(i,1,m) {
		int u=rd(),v=rd();
		AddEdge(u,v),AddEdge(v,u);
		rep(j,1,n+k) G[j][i*2]=G[j][i*2+1]=1;
	}
	int ans=0;
	rep(_,1,k) {
		int u=a[_];
		rep(i,1,n+k) rep(j,1,n) dis[i][j]=INF;
		dis[1][u]=0,que.push(mp(1,u));
		int tu=1,ti=-1,mi=1e9;
		while(!que.empty()) {
			int t=que.front().first,u=que.front().second; que.pop();
			inq[t][u]=0;
			if(u==1 && dis[t][u]<mi) mi=dis[t][u],ti=t,tu=u;
			if(t>1 && W[t-1][u]) Upd(t-1,u,dis[t][u]-C,1001);
			if(t<n+k) Upd(t+1,u,dis[t][u]+C,1002);
			for(int i=head[u];i;i=e[i].nxt) {
				int v=e[i].to;
				if(G[t-1][i^1]>1) Upd(t-1,v,dis[t][u]-(G[t-1][i^1]-2)*D-C,-(i^1));
				if(t<n+k) Upd(t+1,v,dis[t][u]+G[t][i]*D+C,i);
			}
		}
		ans+=mi;
		while(tu!=u || ti!=1) {
			int t=pre[ti][tu];
			if(t==1001) --W[ti++][tu];
			else if(t==1002) W[--ti][tu]++;
			else if(t<0) G[ti][-t]-=2,tu=e[-t].to,ti++;
			else G[ti-1][t]+=2,tu=e[t^1].to,ti--;
		}
	}
	printf("%d\n",ans);
}