经典题,求去掉若干个点,使得两个点不在连通,总价值最少
所以拆点最小割,除了拆点边,流量都为无穷,拆点边是流量为价值
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long LL;
const int maxn=4e2+;
const int INF=0x3f3f3f3f;
struct Edge
{
int from,to,cap,flow;
Edge(int u,int v,int c,int d):from(u),to(v),cap(c),flow(d) {}
};
struct dinic
{
int s,t;
vector<Edge>edges;
vector<int>G[maxn];
int d[maxn];
int cur[maxn];
bool vis[maxn];
void init(){
edges.clear();
for(int i=;i<maxn;++i)
G[i].clear();
}
bool bfs()
{
memset(vis,,sizeof(vis));
queue<int>q;
q.push(s);
d[s]=;
vis[s]=;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=; i<G[x].size(); i++)
{
Edge &e= edges[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow)
{
vis[e.to]=;
d[e.to]=d[x]+;
q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x,int a)
{
if(x==t||a==)return a;
int flow=,f;
for(int &i=cur[x]; i<G[x].size(); i++)
{
Edge &e=edges[G[x][i]];
if(d[x]+==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow))))
{
e.flow+=f;
edges[G[x][i]^].flow-=f;
flow+=f;
a-=f;
if(a==)break;
}
}
return flow;
}
int maxflow(int s,int t)
{
this->s=s;
this->t=t;
int flow=;
while(bfs())
{
memset(cur,,sizeof(cur));
flow+=dfs(s,INF);
}
return flow;
}
void addedge(int u,int v,int c)
{
Edge x(u,v,c,),y(v,u,,);
edges.push_back(x);
edges.push_back(y);
int l=edges.size();
G[u].push_back(l-);
G[v].push_back(l-);
}
}solve;
int a[maxn/];
int main()
{
int n,m,s,t;
while(~scanf("%d%d",&n,&m)){
scanf("%d%d",&s,&t);
for(int i=;i<=n;++i)
scanf("%d",&a[i]);
solve.init();
for(int i=;i<=m;++i){
int u,v;
scanf("%d%d",&u,&v);
solve.addedge(u+n,v,INF);
solve.addedge(v+n,u,INF);
}
for(int i=;i<=n;++i)
solve.addedge(i,i+n,a[i]);
printf("%d\n",solve.maxflow(s,t+n));
}
return ;
}