题意：
有一群*要从起点st到en城市集合，你要在路程中的城市阻止他们，使得他们全部都被抓到(当然st城市，en城市也可以抓捕)。在每一个城市抓捕都有一个花费，你要找到花费最少是多少。
题解：
1 //首先这一道题我原本是想这用bfs来做，因为这就相当于一棵树，你就只需要找出来怎么把它截断就可以
2 //但是这种方法我没有尝试，我还是用的最大流。那个每一个城市可以拆点成两个，然后这两个城市之间的
3 //权值设为这个城市的驻扎成本，然后如果两个城市相连，比如x和y相连，那么就可以建(x+n,y,INF),(y+n,x,INF)这
4 //两条边.然后跑最大流就可以了
5 //即使题目让你求都在哪几个点设防，你也可以写出来。因为跑完最大流之后要设防的点的流量都变成了0
6 #include<stdio.h>
7 #include<string.h>
8 #include<iostream>
9 #include<algorithm>
10 #include<queue>
11 using namespace std;
12 const int maxn=1200;
13 const int INF=0x3f3f3f3f;
14 int head[maxn],cnt,st,en,dis[maxn],cur[maxn];
15 struct edge
16 {
17 int v,next,c,flow;
18 } e[maxn*maxn];
19 void add_edge(int x,int y,int z)
20 {
21 e[cnt].v=y;
22 e[cnt].c=z;
23 e[cnt].flow=0;
24 e[cnt].next=head[x];
25 head[x]=cnt++;
26 }
27 bool bfs()
28 {
29 memset(dis,0,sizeof(dis));
30 dis[st]=1;
31 queue<int>r;
32 r.push(st);
33 while(!r.empty())
34 {
35 int x=r.front();
36 r.pop();
37 for(int i=head[x]; i!=-1; i=e[i].next)
38 {
39 int v=e[i].v;
40 if(!dis[v] && e[i].c>e[i].flow)
41 {
42 dis[v]=dis[x]+1;
43 r.push(v);
44 }
45 }
46 }
47 return dis[en];
48 }
49 int dinic(int s,int limit)
50 {
51 if(s==en || !limit) return limit;
52 int ans=0;
53 for(int &i=cur[s]; i!=-1; i=e[i].next)
54 {
55 int v=e[i].v,feed;
56 if(dis[v]!=dis[s]+1) continue;
57 feed=dinic(v,min(limit,e[i].c-e[i].flow));
58 if(feed)
59 {
60 e[i].flow+=feed;
61 e[i^1].flow-=feed;
62 limit-=feed;
63 ans+=feed;
64 if(limit==0) break;
65 }
66 }
67 if(!ans) dis[s]=-1;
68 return ans;
69 }
70 int main()
71 {
72 int s,d,n,m;
73 while(~scanf("%d%d",&n,&m))
74 {
75 scanf("%d%d",&s,&d);
76 memset(head,-1,sizeof(head));
77 cnt=0;
78 int x;
79 for(int i=1;i<=n;++i)
80 {
81 scanf("%d",&x);
82 add_edge(i,i+n,x);
83 add_edge(i+n,i,0);
84 }
85 st=s;
86 en=d+n;
87 while(m--)
88 {
89 int x,y;
90 scanf("%d%d",&x,&y);
91 add_edge(x+n,y,INF);
92 add_edge(y,x+n,0); //反向边也要建
93 add_edge(y+n,x,INF);
94 add_edge(x,y+n,0);
95 }
96 int ans=0;
97 while(bfs())
98 {
99 for(int i=0; i<=2*n; i++)
100 cur[i]=head[i];
101 ans+=dinic(st,INF);
102 }
103 printf("%d\n",ans);
104 }
105 return 0;
106 }