题目大意：有一个间谍要将一些机密文件送到目的地
现在给出间谍的初始位置和要去的目的地，要求你在间谍的必经路上将其拦获且费用最小

解题思路：最小割最大流的应用，具体可以看网络流–最小割最大流

建图的话
超级源点–起始城市，容量为INF
城市拆成两点(u, v),容量为监视该城市的代价
能连通的城市连接，容量为INF
目的地和超级汇点相连，容量为INF

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; #define N 1010 #define INF 0x3f3f3f3f struct Edge { int from, to, cap, flow; Edge() {} Edge(int from, int to, int cap, int flow): from(from), to(to), cap(cap), flow(flow) {} }; struct ISAP { int p[N], num[N], cur[N], d[N]; int t, s, n, m; bool vis[N]; vector
        
          G[N]; vector
         
           edges; void init(int n) { this->n = n; for (int i = 0; i <= n; i++) { G[i].clear(); d[i] = INF; } edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue
          
            Q; d[t] = 0; vis[t] = 1; Q.push(t); while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i] ^ 1]; if (!vis[e.from] && e.cap > e.flow) { vis[e.from] = true; d[e.from] = d[u] + 1; Q.push(e.from); } } } return vis[s]; } int Augment() { int u = t, flow = INF; while (u != s) { Edge &e = edges[p[u]]; flow = min(flow, e.cap - e.flow); u = edges[p[u]].from; } u = t; while (u != s) { edges[p[u]].flow += flow; edges[p[u] ^ 1].flow -= flow; u = edges[p[u]].from; } return flow; } int Maxflow(int s, int t) { this->s = s; this->t = t; int flow = 0; BFS(); if (d[s] > n) return 0; memset(num, 0, sizeof(num)); memset(cur, 0, sizeof(cur)); for (int i = 0; i < n; i++) if (d[i] < INF) num[d[i]]++; int u = s; while (d[s] <= n) { if (u == t) { flow += Augment(); u = s; } bool ok = false; for (int i = cur[u]; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (e.cap > e.flow && d[u] == d[e.to] + 1) { ok = true; p[e.to] = G[u][i]; cur[u] = i; u = e.to; break; } } if (!ok) { int Min = n; for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (e.cap > e.flow) Min = min(Min, d[e.to]); } if (--num[d[u]] == 0) break; num[d[u] = Min + 1]++; cur[u] = 0; if (u != s) u = edges[p[u]].from; } } return flow; } }; ISAP isap; int n, m; void solve() { int source = 0, sink = 2 * n + 1; int s, t; isap.init(sink); scanf(%d%d, &s, &t); isap.AddEdge(source, s, INF); isap.AddEdge(t + n, sink, INF); int x, y; for (int i = 1; i <= n; i++) { scanf(%d, &x); isap.AddEdge(i, i + n, x); } for (int j = 0; j < m; j++) { scanf(%d%d, &x, &y); isap.AddEdge(x + n, y, INF); isap.AddEdge(y + n, x, INF); } printf(%d , isap.Maxflow(source, sink)); } int main() { while (scanf(%d%d, &n, &m) != EOF) { solve(); } return 0; } 
          
         
        
       
      
     
    
   

?