非常经典的网络流模型。
最大权闭合子图
我们将样例用图的形式表达
5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3接下来我们引入有向图的闭合子图的概念
定义一个有向图的闭合图（closure）\(G=(V,E)\)是该有向图的一个点集，且该点集的所有出边都还指向该点集。即闭合图内的任意点的任意后继也一定在闭合图中。
在本图中，如果我们选择了左边的一个点，那么其后继一定也要被选中。这就是有向图的闭合子图。事实上，我们可以将其转化为最小割的模型。我们将正权点连向源点\(S\)，边权为点权，负权点连向汇点\(T\)，边权为点权的绝对值，而原来的边的权值为\(INF\)。如下图：
我们使用最小割，中间的不可割，左边割了就意味着放弃了第\(i\)名用户的权益，右边割了就意味着建第\(i\)个基站。最后，所有正权点的点权之和减去得到的最小割即为答案。
求最小割可以用“最大流=最小割”定理解决。
上代码
//1为源点，2~1+m为用户，2+m~n+m+1为第i个基站，n+m+2为汇点
#include<bits/stdc++.h>
#define inf 2147483647
#define T n+m+2
#define N 400000
using namespace std;
int cc,to[N],net[N],fr[N],len[N],fx[N],c[N],q[N];
bool vis[N];int n,m,a,u,v,l,sum;
void addedge(int u,int v,int l)
{
cc++;
to[cc]=v;net[cc]=fr[u];fr[u]=cc;len[cc]=l;fx[cc]=cc+1;
cc++;
to[cc]=u;net[cc]=fr[v];fr[v]=cc;len[cc]=0;fx[cc]=cc-1;
}//建边
bool bfs()
{
int h=1,t=1;
for (int i=1;i<=T;i++)
c[i]=0,vis[i]=false;
q[1]=1;c[1]=1;vis[1]=true;
while (h<=t)
{
for (int i=fr[q[h]];i;i=net[i])
{
if (vis[to[i]]||(!len[i])) continue;
q[++t]=to[i];
c[to[i]]=c[q[h]]+1;vis[to[i]]=true;
}
h++;
}
return vis[T];
}
int dfs(int x,int k)
{
int ff=0;
if (x==T) return k;
for (int i=fr[x];i;i=net[i])
{
if (len[i]&&c[to[i]]==c[x]+1)
{
int y=min(k,len[i]);
int re=dfs(to[i],y);
len[i]-=re;
len[fx[i]]+=re;
ff+=re;k-=re;
}
if (k<=0) break;
}
return ff;
}
int dinic()
{
int ans=0;
while (bfs())
{
ans+=dfs(1,inf);
}
return ans;
} //跑dinic
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d",&a);
addedge(m+1+i,T,a);
}
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&l);
sum+=l;
addedge(1,1+i,l);
addedge(1+i,1+m+u,inf);
addedge(1+i,1+m+v,inf);
}
cout<<sum-dinic();
return 0;
} 参考资料
[1] 胡伯涛 《最小割模型在信息学竞赛中的应用》2007