题解

思路分析

这是一道 最小割 + 点权转边权 的网络流问题。

问题建模

• 给定一个无向图，每个点有监控费用
• 需要选择最小费用的点集，使得从起点到终点的所有路径都经过至少一个被监控的点
• 输出被监控的点集

核心思路

1. 最小割模型

这是一个经典的最小点割问题：

• 源点 $s$ = 港口（起点）
• 汇点 $t$ = 仓库（终点）
• 目标：找到最小费用的点集，删除后 $s$ 和 $t$ 不连通

2. 点权转边权

网络流的最小割是边割，而题目要求点割。转化方法：

拆点技巧：

• 将每个点 $i$ 拆成两个点：$i_{\text{in}}$ 和 $i_{\text{out}}$
• 连接有向边 $(i_{\text{in}}, i_{\text{out}})$，容量为点 $i$ 的费用
• 原图中的边 $(i, j)$ 转化为 $(i_{\text{out}}, j_{\text{in}})$ 和 $(j_{\text{out}}, i_{\text{in}})$，容量为 $\infty$

3. 最小割求解

• 使用 Dinic 算法求最小割
• 最小割 = 最大流

4. 构造方案

求出最小割后，找到被割的边（容量非零但残量为0的边）：

• 如果边 $(i_{\text{in}}, i_{\text{out}})$ 被割，说明点 $i$ 被监控
• 通过 DFS 找到从源点可达的点集 $S$
• 被割的点 = 在 $S$ 中的 $i_{\text{in}}$ 但不在 $S$ 中的 $i_{\text{out}}$

算法步骤

1. 拆点建图：

   • 点 $i$ 拆成 $i$ 和 $i+n$
   • 连边 $(i, i+n)$，容量 = 费用
   • 原边 $(u,v)$ 转化为 $(u+n, v)$ 和 $(v+n, u)$，容量 = $\infty$

2. 最大流算法（Dinic）：

   • BFS 分层
   • DFS 增广
   • 求出最大流（= 最小割）

3. DFS 找割边：

   • 从源点 DFS，找到所有可达点
   • 输出满足条件的点

复杂度分析

• Dinic 时间复杂度：$O(n^2 m)$
• 总时间复杂度：$O(n^2 m)$
• 空间复杂度：$O(n + m)$

#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define ri register int
#define fo(i,x,y) for(ri i=(x);i<=(y);++i)
#define fu(i,x,y) for(ri i=(x);i<(y);++i)
#define fd(i,x,y) for(ri i=(x);i>=(y);--i)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=205,M=2e5+5,inf=2147483647;
int n,m,cnt,S,T,tt=1,to[M],nt[M],hd[M],v[M];
int cur[M],dis[M],q[M],vis[M];
inline void add(ri x,ri y,ri z){
	to[++tt]=y;nt[tt]=hd[x];hd[x]=tt;v[tt]=z;
}
inline void link(ri x,ri y,ri z){
	add(x,y,z);add(y,x,0);
}
inline int bfs(){
	ri h=0,t=1;
	fo(i,1,2*n)cur[i]=hd[i],dis[i]=inf;
	dis[S]=0;q[1]=S;
	while(h<t){
		ri x=q[++h];
		for(ri i=hd[x];i;i=nt[i]){
			ri y=to[i];
			if(dis[y]==inf&&v[i]){
				dis[y]=dis[x]+1;
				q[++t]=y;
			}
		}
	}
	return dis[T]!=inf;
}
inline int dfs(ri x,ri fw){
	if(x==T||!fw)return fw;
	ri nd=0;
	for(ri i=cur[x];i&&fw;i=nt[i]){
		ri y=to[i];cur[x]=i;
		if(dis[y]==dis[x]+1&&v[i]){
			ri Fw=dfs(y,min(v[i],fw));
			if(!Fw)dis[y]=inf;
			else{
				nd+=Fw;fw-=Fw;
				v[i]-=Fw;v[i^1]+=Fw;
			}
		}
	}
	return nd;
}
inline void dfs2(ri x){
	vis[x]=1;
	for(ri i=hd[x];i;i=nt[i]){
		ri y=to[i];
		if(!vis[y]&&v[i])dfs2(y);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	scanf("%d%d",&S,&T);T+=n;
	fo(i,1,n){
		ri x;scanf("%d",&x);
		link(i,i+n,x);
	}
	fo(i,1,m){
		ri x,y;scanf("%d%d",&x,&y);
		link(x+n,y,inf);
		link(y+n,x,inf);
	}
	while(bfs()){
		dfs(S,inf);
	}
	dfs2(S);
	for(ri i=2;i<=2*n;i+=2)if(!vis[to[i]]&&vis[to[i^1]])printf("%d ",i/2);
}

题解

把“挑选最小费用的收费站集合拦截所有从港口到仓库的路径”建模成最小割问题：每个收费站拆成“进入点”与“离开点”，两者之间连一条容量为管控成本的边；原图中的无向公路则在拆点后变成两条容量为无穷的有向边。这样从源点（港口邻近收费站的入口）到汇点（仓库邻近收费站的出口）的任意 $s$-$t$ 路径都必须经过某条“进入→离开”的有容量边，切断这些边的最小总代价就是答案。

代码使用 Dinic 求最小割：边 link(i, i+n, cost) 表示拆点的容量边，link(x+n, y, inf) 和 link(y+n, x, inf) 表示双向公路，$S$ 与 $T$ 分别是港口入口和仓库出口。最大流求完以后，对残量网络从源点做一次 DFS，标记仍能到达的点；若某个收费站的入口可达但出口不可达，则其拆点边被割断，这个收费站位于最小割集合。按节点编号输出这些收费站即可。

由于图只有 $200$ 个结点、$2\times10^4$ 条边，Dinic 足以在极短时间内收敛。

#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define ri register int
#define fo(i,x,y) for(ri i=(x);i<=(y);++i)
#define fu(i,x,y) for(ri i=(x);i<(y);++i)
#define fd(i,x,y) for(ri i=(x);i>=(y);--i)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=205,M=2e5+5,inf=2147483647;
int n,m,cnt,S,T,tt=1,to[M],nt[M],hd[M],v[M];
int cur[M],dis[M],q[M],vis[M];
inline void add(ri x,ri y,ri z){
	to[++tt]=y;nt[tt]=hd[x];hd[x]=tt;v[tt]=z;
}
inline void link(ri x,ri y,ri z){
	add(x,y,z);add(y,x,0);
}
inline int bfs(){
	ri h=0,t=1;
	fo(i,1,2*n)cur[i]=hd[i],dis[i]=inf;
	dis[S]=0;q[1]=S;
	while(h<t){
		ri x=q[++h];
		for(ri i=hd[x];i;i=nt[i]){
			ri y=to[i];
			if(dis[y]==inf&&v[i]){
				dis[y]=dis[x]+1;
				q[++t]=y;
			}
		}
	}
	return dis[T]!=inf;
}
inline int dfs(ri x,ri fw){
	if(x==T||!fw)return fw;
	ri nd=0;
	for(ri i=cur[x];i&&fw;i=nt[i]){
		ri y=to[i];cur[x]=i;
		if(dis[y]==dis[x]+1&&v[i]){
			ri Fw=dfs(y,min(v[i],fw));
			if(!Fw)dis[y]=inf;
			else{
				nd+=Fw;fw-=Fw;
				v[i]-=Fw;v[i^1]+=Fw;
			}
		}
	}
	return nd;
}
inline void dfs2(ri x){
	vis[x]=1;
	for(ri i=hd[x];i;i=nt[i]){
		ri y=to[i];
		if(!vis[y]&&v[i])dfs2(y);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	scanf("%d%d",&S,&T);T+=n;
	fo(i,1,n){
		ri x;scanf("%d",&x);
		link(i,i+n,x);
	}
	fo(i,1,m){
		ri x,y;scanf("%d%d",&x,&y);
		link(x+n,y,inf);
		link(y+n,x,inf);
	}
	while(bfs()){
		dfs(S,inf);
	}
	dfs2(S);
	for(ri i=2;i<=2*n;i+=2)if(!vis[to[i]]&&vis[to[i^1]])printf("%d ",i/2);
}