题解

把“挑选最小费用的收费站集合拦截所有从港口到仓库的路径”建模成最小割问题：每个收费站拆成“进入点”与“离开点”，两者之间连一条容量为管控成本的边；原图中的无向公路则在拆点后变成两条容量为无穷的有向边。这样从源点（港口邻近收费站的入口）到汇点（仓库邻近收费站的出口）的任意 $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);
}