【2023北京集训1】apers 做题记录

有一个 $n$ 个点 $m$ 条边有向图，每个点有一个炸毁代价 $c_i$。

给定 $k$、起点 $s$ 和终点 $t$，你需要花费最小的代价使得 $s$ 到 $t$ 至少要经过 $k$ 次被炸毁的点。

保证 $s$ 与 $t$ 联通，无解输出 $-1$。

$1\le n\le 200$，$1\le m\le 500$，$1\le k\le 5$。

考虑最优解中 $s$ 到 $t$ 经过最少炸毁点的路径上的炸毁点序列 $b$。对于一个被炸毁的点 $u$，设 $s$ 到 $u$ 最少经过 $a_u$ 个被炸毁的点，那么若 $u$ 在 $b$ 中出现就一定是第 $a_u$ 个出现，因为走去别的炸毁点再走回来一定不优。

那么建 $k$ 层图，第 $i$ 层的点 $u$ 拆成入点 $u_{i,0}$ 和出点 $u_{i,1}$。

对于一个点 $u$：

• 在第 $i$ 层连边 $(u_{i,0},u_{i,1},c_u)$；
• 在第 $i$ 层连边 $(u_{i,0},u_{i+1,1},\inf)$；

对于原图的一条边 $u\to v$：

• 在第 $i$ 层连边 $(u_{i,1},v_{i,0},\inf)$；

跑 $s_{1,0}$ 到 $t_{k,1}$ 的最小割即可。

具体的，若边权为 $c_u$ 的边未被割掉则可以在同层走，否则一定要向上走一层。而根据前面的结论，同一个点的 $c_u$ 边只可能被割掉一条，所以是对的。

参考代码：

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

const int S=10005,MS=500005;
const int inf=1e8;

int n,m,k;
int st,ed;
vector<int> g[S];
int s,t;
int esum=1,to[MS],c[MS],nxt[MS],h[S];
int dep[S],cur[S];

inline void init(int ns,int nt)
{
	for(int i=s;i<=t;i++) h[i]=0;
	s=ns,t=nt;
	esum=1;
}

inline void added(int x,int y,int w)
{
	to[++esum]=y;
	c[esum]=w;
	nxt[esum]=h[x];
	h[x]=esum;
}

inline void add(int x,int y,int w)
{
	added(x,y,w),added(y,x,0);
}

inline bool bfs()
{
	for(int i=s;i<=t;i++) dep[i]=0,cur[i]=h[i];
	queue<int> q;
	dep[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		if(u==t) return true;
		for(int i=h[u];i;i=nxt[i])
		{
			int v=to[i],w=c[i];
			if(w>0&&dep[v]==0)
			{
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return false;
}

int dfs(int u,int w)
{
	if(u==t) return w;
	int sum=0;
	for(int &i=cur[u];i;i=nxt[i])
	{
		if(c[i]==0) continue;
		int v=to[i];
		if(dep[v]!=dep[u]+1) continue;
		int r=dfs(v,min(c[i],w));
		c[i]-=r;
		c[i^1]+=r;
		w-=r;
		sum+=r;
		if(w==0) break;
	}
	if(sum==0) dep[u]=0;
	return sum;
}

inline int dinic()
{
	int res=0;
	while(bfs()) res+=dfs(s,inf);
	return res;
}

inline int id(int tp,int i,int t)
{
	return (tp-1)*n*2+(i-1)*2+t;
}

int main()
{
	freopen("apers.in","r",stdin);
	freopen("apers.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	scanf("%d%d",&st,&ed);
	init(0,k*n*2+1);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		for(int j=1;j<=k;j++)
		{
			int u=id(j,i,1),v=id(j,i,2);
			add(u,v,x);
		}
		for(int j=1;j<=k-1;j++)
		{
			int u=id(j,i,1),v=id(j+1,i,2);
			add(u,v,inf);
		}
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y); 
		for(int j=1;j<=k;j++)
		{
			int u=id(j,x,2),v=id(j,y,1);
			add(u,v,inf);
		}
	}
	add(s,id(1,st,1),inf);
	add(id(k,ed,2),t,inf);
	queue<int> q;
	dep[st]=1;
	q.push(st);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		if(u==ed)
		{
			if(dep[u]<k) return puts("-1"),0;
			else break;
		}
		for(int v:g[u])
		{
			if(dep[v]==0)
			{
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	printf("%d\n",dinic());
	return 0;
}