自动搬运

查看原文

来自洛谷，原作者为

	xixisuper 老八可爱捏 | 塞苏帕 XI 世

搬运于2025-08-24 23:08:08，当前版本为作者最后更新于2025-01-18 10:47:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P11531 [THUPC2025 初赛] 检查站 题解

鲜花：考场上两名队友在开考 2h 时开始死磕这道题，磕到最后一无所有，本人当时太菜，没学网络流，今重新读题做题，25min 切掉了本题，不知道考场上他俩在想什么。

思路

注意到问题可以看成最小割模型，即通过花费一定的代价割掉一些边，把点集分成两个不相交的子集，令 $1$ 号节点和 $n$ 号节点分别处于不同的两个部分，求最少需要的花费。

考虑建模，题目要求的是把分部割掉，并花费 $1$ 的代价，所以我们考虑把分部拆成两个节点，一个节点只负责接入边，另一个节点只负责接出边。对于第 $i$ 个分部，我们称其直接入边的节点叫做 $I_i$，只接出边的节点叫做 $O_i$，并连接一条 $I_i\to O_i$ 且容量为 $1$ 的边。

对于题面当中的一条铁轨来说，我们这样进行连边：

• 连接一条 $u\to I_r$ 且容量为 $+\infin$ 的边。
• 连接一条 $O_r\to v$ 且容量为 $+\infin$ 的边。

然后在这个网络图上跑 Dinic 就可以了。

建模正确性论证

我们来论证一下上述建模方法的正确性，简单地说，我们希望找到一种建模方式，使得删掉一个分部之后，所有由该分部控制的铁轨都断掉，并且该建模方式不影响原图的连通性。

采用上述建模方式，第一点要求是显然能够满足的，因为割掉 $I_i\to O_i$ 这条边后，所有由 $i$ 控制的铁路肯定都断了。考虑第二点要求，由于题目当中说 $p_r=u$ 或者 $p_r=v$ 必然满足其一，所以可能产生的不在原图中的铁轨有且仅有 $p\to p$ 这种环，但是这种环显然对连通性没有任何影响，所以直接这么建模就是对的。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#define ll int
using namespace std;
const ll N=2e5+10;
const ll M=N<<2;
const ll INF=2147483647;
struct node{ll v,S,nxt;}e[M];
ll head[N],tot=1;
void add_edge(ll from,ll to,ll C){
	e[++tot]={to,C,head[from]};
	head[from]=tot;
}
//1~n station
//n+1~n+c part_in
//n+c+1~n+2c part_out 
ll n,m,c,pt=n,pls[N],S,T;
ll cur[N],dep[N];
bool bfs(){
	for(ll i=1;i<=n+2*c;i++) dep[i]=0;
	queue<ll> qu;
	qu.push(S);dep[S]=1;
	while(!qu.empty()){
		ll v,now=qu.front();qu.pop();
		for(ll i=head[now];i;i=e[i].nxt){
			v=e[i].v;
			if(dep[v]||!e[i].S) continue;
			dep[v]=dep[now]+1;
			if(v==T) return 1;
			qu.push(v);
		}
	}
	return 0;
}
inline ll dfs(ll now,ll MX){
	if(T==now) return MX;
	ll sum=0,linO,v;
	for(ll i=cur[now];i;i=e[i].nxt){
		cur[now]=i;v=e[i].v;
		if(dep[v]!=dep[now]+1||!e[i].S) continue;
		linO=dfs(v,min(MX,e[i].S));
		e[i].S-=linO,e[i^1].S+=linO;
		MX-=linO,sum+=linO;
		if(!MX) break; 
	}
	if(!sum) dep[now]=0;
	return sum;
}
ll Dinic(){
	ll ret=0;
	while(bfs()){
		for(ll i=1;i<=n+2*c;i++) cur[i]=head[i];
		ret+=dfs(S,INF);
	}
	return ret;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>c;
	S=1,T=n;
	for(ll i=n+1;i<=n+c;i++) add_edge(i,i+c,1),add_edge(i+c,i,0);
	for(ll i=1;i<=c;i++) cin>>pls[i];
	for(ll i=1;i<=m;i++){
		ll u,v,r;
		cin>>u>>v>>r;
		add_edge(u,r+n,INF);add_edge(r+n,u,0);
		add_edge(n+c+r,v,INF);add_edge(v,n+c+r,0);
	}
	cout<<Dinic();
	return 0;
}