P3872 [TJOI2010] 电影迷
考虑最小割模型，将一部电影放入 \(S\) 看作去看，放入 \(T\) 看作不去看。
先假设将所有体验值是正数的电影全看完。
对于一部体验值为 \(x\) 的电影 \(i\)。
- 若 \(x>0\)，不去看它则总体验值会减少 \(x\)，相当于放入 \(T\) 部需要 \(x\) 的代价，连边 \((S\to i,x)\)。
- 若 \(x\le0\)，去看它则总体验值会减少 \(-x\)，相当于放入 \(S\) 部需要 \(-x\) 的代价，连边 \((i\to T,-x)\)。
对于两部有依赖关系的电影 \(x,y\)，若看了 \(x\) 没看 \(y\)，即将 \(x\) 选入 \(S\) 部而 \(y\) 选入 \(T\) 部有 \(d_{x,y}\) 的代价。连边 \((x\to y,d_{x,y})\)。
根据最大流最小割定理，按上面建出图后的最大流就是最小代价。
#include<bits/stdc++.h>
using namespace std;
namespace Network{constexpr int N=1005;int n,S,T,gap[N],dep[N];struct edge{int x,w,id;};int maxflow;vector<edge>s[N];vector<edge>::iterator cur[N];void clear(){for(int i=1;i<=n;i++)s[i].clear();n=0;}void add(int u,int v,int w){n=max({n,u,v});int id1=s[u].size();int id2=s[v].size();s[u].push_back({v,w,id2});s[v].push_back({u,0,id1});}void bfs(){queue<int>q;q.emplace(T);memset(gap,0,sizeof gap);memset(dep,-1,sizeof dep);for(gap[dep[T]=0]=1;!q.empty();){int x=q.front();q.pop();for(auto p:s[x]) if(!~dep[p.x])q.push(p.x),gap[dep[p.x]=dep[x]+1]++;}}int dfs(int x,int flow){if(x==T) returnmaxflow+=flow,flow;int res=0;for(auto &it=cur[x];it!=s[x].end();it++){auto &p=*it;if(p.w&&dep[p.x]+1==dep[x]){int t=dfs(p.x,min(flow-res,p.w));p.w-=t,s[p.x][p.id].w+=t,res+=t;if(res==flow) return res;}}gap[dep[x]]--,gap[++dep[x]]++;if(!gap[dep[x]-1]) dep[S]=n;return res;}int ISAP(int st,int ed){for(S=st,T=ed,maxflow=0,bfs();dep[S]<n;dfs(S,INT_MAX))for(int i=1;i<=n;i++) cur[i]=s[i].begin();return maxflow;}
};using Network::add;
constexpr int N=505;
int n,m,ans;
int main(){scanf("%d%d",&n,&m);int S=n+1,T=n+2;for(int i=1,x;i<=n;i++)scanf("%d",&x),x>0?(ans+=x,add(S,i,x)):add(i,T,-x);for(int i=1,x,y,d;i<=m;i++)scanf("%d%d%d",&x,&y,&d),add(x,y,d);printf("%d",ans-Network::ISAP(S,T));return 0;
}