经典题，求去掉若干个点，使得两个点不在连通，总价值最少
所以拆点最小割，除了拆点边，流量都为无穷，拆点边是流量为价值
#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+5; 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=0;i<maxn;++i) G[i].clear(); } bool bfs() { memset(vis,0,sizeof(vis)); queue<int>q; q.push(s); d[s]=0; vis[s]=1; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0; i<G[x].size(); i++) { Edge &e= edges[G[x][i]]; if(!vis[e.to]&&e.cap>e.flow) { vis[e.to]=1; d[e.to]=d[x]+1; q.push(e.to); } } } return vis[t]; } int dfs(int x,int a) { if(x==t||a==0)return a; int flow=0,f; for(int &i=cur[x]; i<G[x].size(); i++) { Edge &e=edges[G[x][i]]; if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))) { e.flow+=f; edges[G[x][i]^1].flow-=f; flow+=f; a-=f; if(a==0)break; } } return flow; } int maxflow(int s,int t) { this->s=s; this->t=t; int flow=0; while(bfs()) { memset(cur,0,sizeof(cur)); flow+=dfs(s,INF); } return flow; } void addedge(int u,int v,int c) { Edge x(u,v,c,0),y(v,u,0,0); edges.push_back(x); edges.push_back(y); int l=edges.size(); G[u].push_back(l-2); G[v].push_back(l-1); } }solve; int a[maxn/2]; int main() { int n,m,s,t; while(~scanf("%d%d",&n,&m)){ scanf("%d%d",&s,&t); for(int i=1;i<=n;++i) scanf("%d",&a[i]); solve.init(); for(int i=1;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=1;i<=n;++i) solve.addedge(i,i+n,a[i]); printf("%d ",solve.maxflow(s,t+n)); } return 0; }