SAP最大流。。额额额额额额额额，看不懂的说，把题解贴出来吧，好歹也能算个模版。。
本题可以看成是求A到B的最大流，因为权值在点上,还要进行拆点。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define MAXM 100000
#define MAXN 405
#define INF 2e9
struct eee{
int v,cap,next;
eee(){};
eee(int v,int w):v(v),cap(w){}
}edge[MAXM];
int first[MAXN];
int d[MAXN];//距离标号
int pre[MAXN];
int numh[MAXN];//GAP数组
int curfirst[MAXN];//各点当前弧
int flow[MAXN];
int e;
int n;
int m;
int S,D;
void init(){
memset(first,-1,sizeof(first));
e=0;
}
void add(int u,int v,int w){
edge[e]=eee(v,w);
edge[e].next=first[u];
first[u]=e++;
edge[e]=eee(u,0);
edge[e].next=first[v];
first[v]=e++;
}
int sap_maxflow(int st,int en){
int ans=0;
for(int i=1;i<=n;i++)
curfirst[i]=first[i];
memset(d,0,sizeof(d));
memset(numh,0,sizeof(numh));
numh[0]=n;
int i=st;
bool ok;
int MIN;
int aug=INF;
while(d[st]<n){
flow[st]=aug;
ok=false;
for(int j=curfirst[i];j!=-1;j=edge[j].next){
if(edge[j].cap&&d[i]==d[edge[j].v]+1){
ok=true;
aug=min(aug,edge[j].cap);
curfirst[i]=j;
i=edge[j].v;
pre[i]=j;
if(i==en){
ans+=aug;
for(;i!=st;i=edge[pre[i]^1].v){
edge[pre[i]].cap-=aug;
edge[pre[i]^1].cap+=aug;
}
aug=INF;
}
}
}
if(ok)continue;
MIN=n-1;
for(int j=first[i];j!=-1;j=edge[j].next)
if(edge[j].cap&&d[edge[j].v]<MIN){
MIN=d[edge[j].v];
curfirst[i]=j;
}
if(--numh[d[i]]==0)break;
d[i]=MIN+1;
numh[d[i]]++;
if(i!=st){
i=edge[pre[i]^1].v;
aug=flow[i];
}
}
return ans;
}
int main()
{
while(scanf("%d%d",&n,&m)==2){
scanf("%d%d",&S,&D);
init();
int a,b;
add(0,S,INF);//增加超级源点
add(D+n,2*n+1,INF);//增加超级汇点
for(int i=1;i<=n;i++){
scanf("%d",&a);
add(i,i+n,a);
add(i+n,i,a);
}
for(int i=0;i<m;i++){
scanf("%d%d",&a,&b);
add(a+n,b,INF);
add(b+n,a,INF);
}
S=0;D=2*n+1;
n=n*2+2;
printf("%d\n",sap_maxflow(S,D));
}
return 0;
}