学步园

题意：有N个城市 M条无向边　有一恐怖分子要从某一城市到另一城市　打算在某些城市安放一些SA 去抓住他
但若在某个城市安放SA需要一定费用 求要抓到恐怖分子 最少的费用是多少？

思路：网络流问题。建一超级源点和汇点与原源点、汇点相连，然后把一个城市拆成两个点 边权为其费用
两相连城市间的边权为无穷大  求其最大流即可。

//62MS   
1176K

#include <stdio.h>
#include <string.h>
#define L(u) ((u) << 1)
#define R(u) ((u) << 1 | 1)
#define VM 420
#define EM 100000
#define inf 0x3f3f3f3f
struct E
{
    int
to,cap,nxt;
}edge[EM];

int head[VM],gap[VM],dist[VM],cur[VM],pre[VM];
int e,src,des,n,m;
void addedge (int cu,int cv,int cw)
{

    edge[e].to =
cv;
    edge[e].cap
= cw;
    edge[e].nxt
= head[cu];
    head[cu] =
e;
    e ++;
    edge[e].to =
cu;
    edge[e].cap
= 0;
    edge[e].nxt
= head[cv];
    head[cv] =
e;
    e ++;
}
int min (int a ,int b)
{
   return a > b ?
b : a;
}

int sap ()
{
    memset
(dist,0,sizeof(dist));
    memset
(gap,0,sizeof (dist));
    memcpy
(cur,head,sizeof(dist));
    int res =
0;
    int u =
pre[src] = src;
    int aug =
inf;
    gap[0] =
n;
    while
(dist[src] < n)
    {
loop:
       
for (int &i = cur[u];i != -1;i = edge[i].nxt)
       
{
           
int v = edge[i].to;
           
if (edge[i].cap && dist[u] ==
dist[v] + 1)
           
{
               
aug = min (aug,edge[i].cap);
               
pre[v] = u;
               
u = v;
               
if (v == des)
               
{
                   
res += aug;
                   
for (u = pre[u];v != src;v = u,u = pre[u])
                   
{