题目:洛谷P4174 [NOI2006]最大获利
思路:
最大权闭合子图模型
对本题来说,可以理解为:
首先我们假设所有用户的收益都可以得到,把这些收益加起来,作为初始答案。
但是这些收益肯定不可能不建造中转站就全部得到,我们要么建造一些中转站,要么放弃一些用户。这些都会减少总收益,所以我们要设法让减少量最小。
按下述方法建图:在中转站和它能服务的用户之间连容量为inf的边。添加超级源汇点s、t,从s向所有中转站连边,容量为建造中转站的花费,从所有用户向t连边,容量为该用户收益。
计算出该图的最小割,表示的意义为:显然inf边不会被割掉。所以若割掉s到中转站的边,表示不建造这个中转站;若割掉用户到t的边,表示放弃该用户的收益。
因为是最小割,所以最后的结果最小,相当于让我们放弃的收益最少。
于是用最初的总收益减去最少要放弃的收益(最小割)就得到了答案。
Code:
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5,inf=0x3f3f3f3f;
int n,m,s,t,tot,ans,d[N];
int Top=1,ver[N],nxt[N],val[N],head[N];
inline void add(int u,int v,int w){
ver[++Top]=v;val[Top]=w;nxt[Top]=head[u];head[u]=Top;
ver[++Top]=u;val[Top]=0;nxt[Top]=head[v];head[v]=Top;
}
bool bfs(){
for(int i=1;i<=tot;++i) d[i]=0;
queue<int> q;
q.push(s);
d[s]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=nxt[i]){
int v=ver[i];
if(val[i]&&!d[v]){
d[v]=d[u]+1;
if(v==t) return true;
q.push(v);
}
}
}
return false;
}
int dfs(int u,int flow){
if(u==t) return flow;
int left=flow;
for(int i=head[u];i&&left;i=nxt[i]){
int v=ver[i];
if(val[i]&&d[v]==d[u]+1){
int res=dfs(v,min(left,val[i]));
if(!res) d[v]=0;
val[i]-=res;
val[i^1]+=res;
left-=res;
}
}
return flow-left;
}
int main(){
scanf("%d%d",&n,&m);
tot=n+m;
s=++tot;
t=++tot;
for(int i=1,w;i<=n;++i){
scanf("%d",&w);
add(s,i,w);
}
for(int i=1,a,b,c;i<=m;++i){
scanf("%d%d%d",&a,&b,&c);
add(a,n+i,inf);
add(b,n+i,inf);
add(n+i,t,c);
ans+=c;
}
while(bfs()) ans-=dfs(s,inf);
printf("%d",ans);
return 0;
}