題目連結:http://acm.hdu.edu.cn/showproblem.php?pid=4289
題目大概:
恐怖分子從一個城市要到達另一個城市,要想半路攔截住恐怖恐怖分子,就要控制城市,在恐怖分子來的時候,抓住,每個城市都有費用,問攔截住恐怖分子的最小費用是多少。
思路:
是一道最小割的題。
因為每個城市有價值,可以拆點,來控制流量。
s連開始的城市,容量無窮,最後的城市連t彙點,容量無窮,城市自己和自己建邊,容量為城市價值,城市之間能連通的建雙向邊,容量無窮。
這樣容量有限的隻有城市自己的價值的邊,那麼,最小割隻能割城市的價值了。
跑一遍最大流求最小割。
感想:
這個題,一是注意拆邊,而是注意注意無向圖的雙向邊,然後就是如何構造最小割。
#include <iostream>
#include <cstdio>
#include <cstring>
#define REP(I, X) for(int I = 0; I < X; ++I)
#define FF(I, A, B) for(int I = A; I <= B; ++I)
#define clear(A, B) memset(A, B, sizeof A)
#define copy(A, B) memcpy(A, B, sizeof A)
#define min(A, B) ((A) < (B) ? (A) : (B))
#define max(A, B) ((A) > (B) ? (A) : (B))
using namespace std;
typedef long long ll;
typedef long long LL;
const int oo = 0x3f3f3f3f;
const int maxE = 200050;
const int maxN = 5005;
const int maxQ = 10000;
struct Edge{
int v, c, n;
};
Edge edge[maxE];
int adj[maxN], cntE;
int Q[maxE], head, tail, inq[maxN];
int d[maxN], num[maxN], cur[maxN], pre[maxN];
int s, t, nv;
int n, m, nm;
int path[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
void addedge(int u, int v, int c){
edge[cntE].v = v;edge[cntE].c = c; edge[cntE].n = adj[u]; adj[u] = cntE++;
edge[cntE].v = u;edge[cntE].c = 0; edge[cntE].n = adj[v]; adj[v] = cntE++;
}
void REV_BFS(){
clear(d, -1);
clear(num, 0);
head = tail = 0;
d[t] = 0;
num[0] = 1;
Q[tail++] = t;
while(head != tail){
int u = Q[head++];
for(int i = adj[u]; ~i; i = edge[i].n){
int v = edge[i].v;
if(~d[v]) continue;
d[v] = d[u] + 1;
num[d[v]]++;
Q[tail++] = v;
}
}
}
int ISAP(){
copy(cur, adj);
REV_BFS();
int flow = 0, u = pre[s] = s, i;
while(d[s] < nv){
if(u == t){
int f = oo, neck;
for(i = s; i != t; i = edge[cur[i]].v){
if(f > edge[cur[i]].c){
f = edge[cur[i]].c;
neck = i;
}
}
for(i = s; i != t; i = edge[cur[i]].v){
edge[cur[i]].c -= f;
edge[cur[i] ^ 1].c += f;
}
flow += f;
u = neck;
}
for(i = cur[u]; ~i; i = edge[i].n) if(edge[i].c && d[u] == d[edge[i].v] + 1) break;
if(~i){
cur[u] = i;
pre[edge[i].v] = u;
u = edge[i].v;
}
else{
if(0 == (--num[d[u]])) break;
int mind = nv;
for(i = adj[u]; ~i; i = edge[i].n){
if(edge[i].c && mind > d[edge[i].v]){
mind = d[edge[i].v];
cur[u] = i;
}
}
d[u] = mind + 1;
num[d[u]]++;
u = pre[u];
}
}
return flow;
}
void work()
{
cntE=0;
clear(adj, -1);
s=0;t=2*n+1;nv=t+1;
int q,w;
scanf("%d%d",&q,&w);
addedge(s,q,oo);
addedge(n+w,t,oo);
int ww;
for(int i=1;i<=n;i++)
{
scanf("%d",&ww);
addedge(i,n+i,ww);
}
int u,v;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
addedge(n+u,v,oo);
addedge(n+v,u,oo);
}
printf("%d\n",ISAP());
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
work();
}
return 0;
}