题意：有n个城市，m条双向边，有一群小偷从s前往t偷东西，警察叔叔们想要逮捕小偷们，现在告诉你在每座城市需要多少警察才能抓住这个城市的小偷，为什么说这个城市，因为小偷们会分开跑；然后题目还说不能在s和t逮捕小偷。问需要的最少警力是多少？
分析：这个问题可以变成这样：需要在哪些城市部署警力才能使得小偷不能从s到达t，也即最小点权割集。根据最小割=最大流(此处的最小割是指边权)，我们可以这样建图。
建图：把除了s和t的每一个点拆开，在它们之间连一条单向边，权值为该点需要的警力。s和t同样拆开，不过权值为无穷大，因为题目说了不能在s和t逮捕。题目给出的边就按双向边相连，不过起点应该是这个点拆开后的终点，权值为无穷大。最后为了方便，可以把源点和s相连，t和汇点相连，权值都为无穷大。至此，就转换成最小割的模型，求出最大流即可。
手写isap写丑了，没有1A。
#include<stdio.h>
#include<string.h>
#define min(x,y) (x)<(y)?(x):(y)
const int N=,M=1e5+,INF=0x3f3f3f3f;
struct node
{
int v,c,next;
}e[M];
int gap[N],h[N],head[N];
int s,t,n,m,cnt;
void init()
{
memset(head,-,sizeof(head));
cnt=;
}
void add(int u,int v,int w)
{
e[cnt].v=v,e[cnt].c=w;
e[cnt].next=head[u],head[u]=cnt++;
e[cnt].v=u,e[cnt].c=;
e[cnt].next=head[v],head[v]=cnt++;
}
int dfs(int u,int flow)
{
if(u==t) return flow;
int a,i,v,c=flow,minh=t;
for(i=head[u];i!=-;i=e[i].next)
{
if(e[i].c)
{
v=e[i].v;
if(h[v]==h[u]-)
{
a=min(c,e[i].c);
a=dfs(v,a);
e[i].c-=a;
e[i^].c+=a;
c-=a;
if(h[s]>t) return flow-c;
if(!c) break;
}
minh=min(minh,h[v]);
}
}
if(c==flow)
{
if(--gap[h[u]]==) h[s]=t+;
++gap[h[u]=minh+];
}
return flow-c;
}
int isap()
{
memset(gap,,sizeof(gap));
memset(h,,sizeof(h));
int ans=;gap[]=t+;
while(h[s]<=t)
ans+=dfs(s,INF);
return ans;
}
int main()
{
int T,u,v,i,ss,tt;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&n,&m,&ss,&tt);
init();s=,t=*n+;
for(i=;i<=n;i++)
{
int x;
scanf("%d",&x);
if(i!=ss&&i!=tt)
add(i,i+n,x);
else
add(i,i+n,INF);
}
while(m--)
{
scanf("%d%d",&u,&v);
add(u+n,v,INF);
add(v+n,u,INF);
}
add(s,ss,INF);add(tt+n,t,INF);
printf("%d\n",isap());
}
return ;
}