[NOI2006]最大获利(最大权闭合子图）
题目描述
新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。
在前期市场调查和站址勘测之后，公司得到了一共 N 个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第 i个通讯中转站需要的成本为 P_iPi （1≤i≤N）。
另外公司调查得出了所有期望中的用户群，一共 M 个。关于第 i 个用户群的信息概括为 A_iAi , B_iBi 和 C_iCi ：这些用户会使用中转站 A i 和中转站 B i 进行通讯，公司可以获益 C_iCi 。（1≤i≤M, 1≤ A_iAi , B_iBi ≤N）
THU 集团的 CS&T 公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 – 投入成本之和）
输入输出格式
输入格式：
输入文件中第一行有两个正整数 N 和 M 。
第二行中有 N 个整数描述每一个通讯中转站的建立成本，依次为 P_1 , P_2 , …,P_NP1,P2,…,PN 。
以下 M 行，第(i + 2)行的三个数 A_i , B_iAi,Bi 和 C_iCi 描述第 i 个用户群的信息。
所有变量的含义可以参见题目描述。
输出格式：
你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。
输入输出样例
说明
样例：选择建立 1、2、3 号中转站，则需要投入成本 6，获利为 10，因此得到最大收益 4。
100%的数据中：N≤5 000，M≤50 000，0≤ C_iCi ≤100，0≤ P_iPi ≤100。
最大权闭合子图。
正权值点连源点，负权值点连汇点，在用户群与站有交集的部分连一条权为inf的边，则答案为正权值总和-最小割。
由最大流-最小割定理，跑Dinic即可。
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
int P[maxn];
const int inf=1e9;
struct Edge
{
int u,v,c,flow;
Edge(int a,int b,int cc,int f):u(a),v(b),c(cc),flow(f){}
};
int n;
struct Dinic
{
int s,t;
vector<Edge> edges;
vector<int> pre[maxn];
bool vis[maxn];
int dist[maxn];
int cur[maxn];
void init()
{
for(int i=0;i<=n+1;i++)
{
pre[i].clear();
}
edges.clear();
}
void Addedge(int u,int v,int f)
{
edges.push_back(Edge(u,v,f,0));
edges.push_back(Edge(v,u,0,0));
int mm=edges.size();
pre[u].push_back(mm-2);
pre[v].push_back(mm-1);
}
bool bfs()
{
memset(vis,false,sizeof(vis));
queue<int> q;
q.push(s);
vis[s]=1;
dist[s]=0;
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=0;i<pre[now].size();i++)
{
Edge &e=edges[pre[now][i]];
if(!vis[e.v]&&e.c>e.flow)
{
dist[e.v]=dist[now]+1;
vis[e.v]=true;
q.push(e.v);
}
}
}
return vis[t];
}
int dfs(int x,int cap)
{
if(x==t||cap==0) return cap;
int f,flow=0;
for(int &i=cur[x];i<pre[x].size();i++)
{
cur[x]=i;
Edge &e=edges[pre[x][i]];
if(dist[e.v]==dist[x]+1&&(f=dfs(e.v,min(cap,e.c-e.flow))))
{
e.flow+=f;
edges[pre[x][i]^1].flow-=f;
flow+=f;
cap-=f;
if(cap==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;
}
}dc;
int main()
{
int n,m,i;
cin>>n>>m;
dc.init();
for(i=1;i<=n;i++)
{
scanf("%d",&P[i]);
}
int x,y,z,temp=0;
for(i=1;i<=m;i++)
{
cin>>x>>y>>z;
temp+=z;
dc.Addedge(0,i,z);
dc.Addedge(i,x+m,inf);
dc.Addedge(i,y+m,inf);
}
for(i=1;i<=n;i++)
{
dc.Addedge(i+m,10+m+n,P[i]);
}
int maxim_flow=dc.Maxflow(0,10+m+n);
int ans=temp-maxim_flow;
cout<<ans<<endl;
return 0;
}