看了这道题，然后重新开始练习自己的刚敲不久的网络流，发现还是难以一遍敲得完整啊，，，，，
调了。。。遍，改了。。。遍，测了。。。遍，交了，，，遍，总算是A了，，不简单啊
然后试着用了其他两种算法EK和dinic都试着去练习一下，慢慢A了，，，真是不简单有木有
题目大意是这样的，有一些小偷打算从城市S到城市T,但是我们不知道他们会走哪些边，为了确保一定可以能够抓住所有的小偷，现在需要在某些城市布置一些警察，已知在城市i布置的花费是P[i],现在要使的抓住小偷的同时我的花费最小，求最小花费。
这里用到了最大流的一个定理，最小割最大流定理：当起点到终点的最大流算出来时，这个最大流就是将图划分为两个互不连通的集合的最小割。证明可以自己百度或看其他神牛的博客。
有了这个定理，就变成了裸的最大流问题了
下面我试着用三种方法做了这道题，比较了一下发现最快的依然是SAP，其次是dinic，最后是EK算法
SAP
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf ((LL)1<<40)
#define lson k<<1, L, mid
#define rson k<<1|1, mid+1, R
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define FOPENIN(IN) freopen(IN, "r", stdin)
#define FOPENOUT(OUT) freopen(OUT, "w", stdout)
template<class T> T ABS ( T a) { return a >= ? a : -a; }
template<class T> T CMP_MIN ( T a, T b ) { return a < b; }
template<class T> T CMP_MAX ( T a, T b ) { return a > b; }
template<class T> T MAX ( T a, T b ) { return a > b ? a : b; }
template<class T> T MIN ( T a, T b ) { return a < b ? a : b; }
template<class T> T GCD ( T a, T b ) { return b ? GCD ( b, a % b ) : a; }
template<class T> T LCM ( T a, T b ) { return a / GCD ( a, b ) * b; }
template<class T> void SWAP( T& a, T& b ) { T t = a; a = b; b = t; } typedef __int64 LL;
//typedef long long LL;
const int MAXN = ;
const int MAXM = ;
const double eps = 1e-;
const double PI = 4.0 * atan(1.0);
const LL MOD = ; #define L(i) (i<<1)
#define R(i) (i<<1|1) int m, n, s, d;
struct Edge { int to, cap, next; }edge[MAXM<<];
int tot, head[MAXN]; int src, des;
int gap[MAXN], dep[MAXN], aug[MAXN], cur[MAXN], pre[MAXN]; void addEdge(int u, int v, int c)
{
edge[tot].to = v; edge[tot].cap = c; edge[tot].next = head[u];
head[u] = tot ++;
edge[tot].to = u; edge[tot].cap = ; edge[tot].next = head[v];
head[v] = tot ++;
} void init()
{
int x, y;
tot = ;
mem1(head); mem0(edge);
scanf("%d %d", &s, &d);
for(int i = ; i <= n; i ++)
{
scanf("%d", &x);
addEdge(L(i), R(i), x);
addEdge(R(i), L(i), x);
}
for(int i = ; i < m; i ++)
{
scanf("%d %d", &x, &y);
addEdge(R(x), L(y), INF);
addEdge(R(y), L(x), INF);
}
src = ;
des = (n+)<<;
addEdge(src, L(s), INF);
addEdge(R(d), des, INF);
} int SAP(int n)
{
mem0(gap);
mem0(dep);
mem0(aug);
mem0(pre);
aug[src] = INF;
pre[src] = -;
gap[] = n;
int max_flow = , u = src;
for(int i = ; i <= n; i ++)
cur[i] = head[i];
while(dep[src] < n)
{
if(u == des)
{
max_flow += aug[des];
for(int v = pre[des]; v != -; v = pre[v])
{
int id = cur[v];
edge[id].cap -= aug[des];
edge[id^].cap += aug[des];
aug[v] -= aug[des];
if(edge[id].cap == )
u = v;
}
}
int flag = ;
for(int i = cur[u]; i != -; i = edge[i].next)
{
int v = edge[i].to;
if(edge[i].cap > && dep[u] == dep[v]+)
{
flag = ;
pre[v]= u;
cur[u] = i;
aug[v] = MIN(aug[u], edge[i].cap);
u = v;
break;
}
}
if(!flag)
{
if(--gap[dep[u]] == )
break;
int min_dep = n;
cur[u] = head[u];
for(int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].to;
if(edge[i].cap > && dep[v] < min_dep)
{
min_dep = dep[v];
cur[u] = i;
}
}
dep[u] = min_dep + ;
gap[dep[u]] ++;
if(pre[u] != -) u = pre[u];
}
}
return max_flow;
} int main()
{
while(~scanf("%d %d", &n, &m))
{
init();
printf("%d\n", SAP(des));
}
return ;
}
dinic
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf ((LL)1<<40)
#define lson k<<1, L, mid
#define rson k<<1|1, mid+1, R
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define FOPENIN(IN) freopen(IN, "r", stdin)
#define FOPENOUT(OUT) freopen(OUT, "w", stdout)
template<class T> T ABS ( T a) { return a >= ? a : -a; }
template<class T> T CMP_MIN ( T a, T b ) { return a < b; }
template<class T> T CMP_MAX ( T a, T b ) { return a > b; }
template<class T> T MAX ( T a, T b ) { return a > b ? a : b; }
template<class T> T MIN ( T a, T b ) { return a < b ? a : b; }
template<class T> T GCD ( T a, T b ) { return b ? GCD ( b, a % b ) : a; }
template<class T> T LCM ( T a, T b ) { return a / GCD ( a, b ) * b; }
template<class T> void SWAP( T& a, T& b ) { T t = a; a = b; b = t; } typedef __int64 LL;
//typedef long long LL;
const int MAXN = ;
const int MAXM = ;
const double eps = 1e-;
const double PI = 4.0 * atan(1.0);
const LL MOD = ; #define L(i) (i<<1)
#define R(i) (i<<1|1) int m, n, s, d;
struct Edge { int to, cap, next; }edge[MAXM<<];
int tot, head[MAXN]; int src, des;
int dis[MAXN]; void addEdge(int u, int v, int c)
{
edge[tot].to = v; edge[tot].cap = c; edge[tot].next = head[u];
head[u] = tot ++;
edge[tot].to = u; edge[tot].cap = ; edge[tot].next = head[v];
head[v] = tot ++;
} void init()
{
int x, y;
tot = ;
mem1(head); mem0(edge);
scanf("%d %d", &s, &d);
for(int i = ; i <= n; i ++)
{
scanf("%d", &x);
addEdge(L(i), R(i), x);
addEdge(R(i), L(i), x);
}
for(int i = ; i < m; i ++)
{
scanf("%d %d", &x, &y);
addEdge(R(x), L(y), INF);
addEdge(R(y), L(x), INF);
}
src = ;
des = (n+)<<;
addEdge(src, L(s), INF);
addEdge(R(d), des, INF);
} bool bfs()
{
queue<int>q;
mem1(dis);
dis[src] = ;
q.push(src);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].to;
if(dis[v] == - && edge[i].cap > )
{
dis[v] = dis[u] + ;
q.push(v);
}
}
}
return dis[des] != -;
} int dfs(int cur, int aug)
{
if(cur == des || aug == )
return aug;
int flow = ;
for(int i = head[cur]; i != -; i = edge[i].next)
{
int v = edge[i].to;
if ( dis[v] == dis[cur]+ && edge[i].cap > )
{
int f = dfs( v, MIN(edge[i].cap, aug) );
edge[i].cap -= f;
edge[i^].cap += f;
flow += f;
aug -= f;
if(aug == )
break;
}
}
return flow;
} int dinic()
{
int res = ;
while (bfs())
{
res += dfs(src, INF);
}
return res;
} int main()
{
//FOPENIN("in.txt");
while(~scanf("%d %d", &n, &m))
{
init();
printf("%d\n", dinic());
}
return ;
}
EK
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf ((LL)1<<40)
#define lson k<<1, L, mid
#define rson k<<1|1, mid+1, R
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define FOPENIN(IN) freopen(IN, "r", stdin)
#define FOPENOUT(OUT) freopen(OUT, "w", stdout)
template<class T> T ABS ( T a) { return a >= ? a : -a; }
template<class T> T CMP_MIN ( T a, T b ) { return a < b; }
template<class T> T CMP_MAX ( T a, T b ) { return a > b; }
template<class T> T MAX ( T a, T b ) { return a > b ? a : b; }
template<class T> T MIN ( T a, T b ) { return a < b ? a : b; }
template<class T> T GCD ( T a, T b ) { return b ? GCD ( b, a % b ) : a; }
template<class T> T LCM ( T a, T b ) { return a / GCD ( a, b ) * b; }
template<class T> void SWAP( T& a, T& b ) { T t = a; a = b; b = t; } typedef __int64 LL;
//typedef long long LL;
const int MAXN = ;
const int MAXM = ;
const double eps = 1e-;
const double PI = 4.0 * atan(1.0);
const LL MOD = ; #define L(i) (i<<1)
#define R(i) (i<<1|1) int n, m, s, d; int src, des;
int cap[MAXN][MAXN], flow[MAXN][MAXN], pre[MAXN], a[MAXN]; void init()
{
int x, y;
src = ;
des = (n+)<<;
mem0(cap);mem0(pre);
scanf("%d %d", &s, &d);
cap[src][L(s)] = INF;
cap[R(d)][des] = INF;
for(int i = ; i <= n; i ++)
{
scanf("%d", &x);
cap[L(i)][R(i)] = x;
cap[R(i)][L(i)] = x;
}
for(int i = ; i < m; i ++)
{
scanf("%d %d", &x, &y);
cap[R(x)][L(y)] = INF;
cap[R(y)][L(x)] = INF;
}
} int EK(int n)
{
queue<int>q;
mem0(flow);
int max_flow = ;
while(true)
{
mem0(a);
a[src] = INF;
q.push(src);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int v = ; v <= n; v ++) if(!a[v] && cap[u][v]>flow[u][v])
{
pre[v]= u;
q.push(v);
a[v] = MIN(a[u], cap[u][v] - flow[u][v]);
}
}
if(a[des] == ) break;
for(int u = des; u != src; u = pre[u])
{
flow[pre[u]][u] += a[des];
flow[u][pre[u]] -= a[des];
}
max_flow += a[des];
}
return max_flow;
} int main()
{
//FOPENIN("in.txt");
while(~scanf("%d %d", &n, &m))
{
init();
printf("%d\n", EK(des));
}
return ;
}