1497: [NOI2006]最大获利（最大权闭合子图）

1497: [NOI2006]最大获利

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 5503  Solved: 2673

Description

新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后，公司得到了一共N个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第i个通讯中转站需要的成本为Pi（1≤i≤N）。另外公司调查得出了所有期望中的用户群，一共M个。关于第i个用户群的信息概括为Ai, Bi和Ci：这些用户会使用中转站Ai和中转站Bi进行通讯，公司可以获益Ci。（1≤i≤M, 1≤Ai, Bi≤N） THU集团的CS&T公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 - 投入成本之和）

Input

输入文件中第一行有两个正整数N和M 。第二行中有N个整数描述每一个通讯中转站的建立成本，依次为P1, P2, …, PN 。以下M行，第(i + 2)行的三个数Ai, Bi和Ci描述第i个用户群的信息。所有变量的含义可以参见题目描述。

Output

你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。

Sample Input

5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3

Sample Output

4

HINT

【样例说明】选择建立1、2、3号中转站，则需要投入成本6，获利为10，因此得到最大收益4。【评分方法】本题没有部分分，你的程序的输出只有和我们的答案完全一致才能获得满分，否则不得分。【数据规模和约定】 80%的数据中：N≤200，M≤1 000。 100%的数据中：N≤5 000，M≤50 000，0≤Ci≤100，0≤Pi≤100。

分析

推荐文章:胡伯涛 《最小割模型在信息学竞赛中的应用》

对于图闭合图建成网络，是：构造一个源点S，汇点T。将S与所有权值为正的点连一条容量为其权值的边，将T所有权值为负的点连一条容量为其权值的绝对值的边，原来的边将其容量定为正无穷。

那么怎么运用到题目上呢，需要进行转化一下。

我们可以理解成：人是正权值的点（有获益），中转站是负权值的的点（建造需要成本），每个人有两个所属的中转站，人和两个中转站之间有两条边。是不是很奇妙

这样就形成了一个闭合图，用上面的话，构造一个源点S，汇点T，正权值点（人）向S连边，容量就是点的权值；负权值点（中转站）向T连边，容量是点权值得绝对；原来的边容量正无穷。

网络图就构造好了，就是下面的图，求出最小割，即最大流，用sum-最大流。sum所有人带来的获益的和（所有正权值点的权值和）

求最小割的意义：

对于这样建图，其实还可以这样理解的，我再补充一下，如果理解求最大权闭合图，就可以做了，可以直接跳过。

我们建好图后，就是下面的图，然后求最小割，为啥求最小割呢（上面文章中有，这是另一种思路）。

求最小割其实就是求最少的花费，sum是所有人的带来的收益和，那么sum把所有的收益加起来了，减去花费不就是最大获益吗？这就是为什么求最小割了。

所以：最小割是花费，要让花费尽量小。

那么求最小割了，设最小割是ans花费，随后要用sum-ans：

• 首先中间的绿边是一定不能切的，切一条绿边的花费就是正无穷了！！！
• 切红边是什么意思呢：表示这个人的收益不要了，不需要满足他了
• 切蓝边：这个中转站建（意会一下，ans+中转站的价格，然后sum再减去，都减去成本，当然建啊）

然后可能有疑问了：会不会我切了红边（不要这个人的收益了），又把属于他的练歌蓝边切了。

当然不可能，绿边可不是凑了闹的，比如对于点a1,他有两条边s-a1-b1-t，s-a1-b2-t,如果切了s-a1这两条边已经断开了，再切b1-t,b2-t没什么用。

好了，到这了，突然发现打了这么多字，可能表达不清楚，qwq

code

 #include<cstdio>
 #include<algorithm>
 #include<queue>
 #include<cstring>

 using namespace std;

 const int MAXN = ;
 const int INF = 0x7fffffff;
 struct Edge{
     int to,nxt,c;
 }e[];
 int sum,tot = ,n,m,s,t,ans;
 int head[MAXN], val[MAXN],dis[MAXN];
 queue<int>q;

 int read()
 {
     int x = ,f = ;char ch = getchar();
     for (; ch<''||ch>''; ch = getchar())
         if (ch=='-') f = -;
     for (; ch>=''&&ch<=''; ch = getchar())
         x = x*+ch-'';
     return x*f;
 }
 void add_edge(int u,int v,int w)
 {
     ++tot;
     e[tot].c = w,e[tot].to = v,e[tot].nxt = head[u];
     head[u] = tot;
     ++tot;
     e[tot].c = ,e[tot].to = u,e[tot].nxt = head[v];
     head[v] = tot;
 }
 bool bfs()
 {
     memset(dis,-,sizeof(dis));
     q.push(s);
     dis[s] = ;
     while (!q.empty())
     {
         int u = q.front();
         q.pop();
         for (int i=head[u]; i; i=e[i].nxt)
         {
             int v = e[i].to;
             if (dis[v]==- && e[i].c>)
             {
                 dis[v] = dis[u]+;
                 q.push(v);
             }
         }
     }
     if (dis[t]!=-) return true;
     return false;
 }
 int dfs(int u,int low)
 {
     if (u==t) return low;
     int w ,tmp = low;
     for (int i=head[u]; i; i=e[i].nxt)
     {
         int v = e[i].to;
         if (dis[v]==dis[u]+ && e[i].c> )
         {
             w = dfs(v,min(low,e[i].c));
             e[i].c -= w;
             e[i^].c += w;
             low -= w;
         }
     }
     return tmp - low;
 }
 int main()
 {
     n = read();m = read();
     s = ,t = n+m+;
     for (int x,i=; i<=n; ++i)
     {
         x = read();
         add_edge(i+m,t,x);//建立从中转站到T的边，中转站的花费
     }
     for (int x,y,z,i=; i<=m; ++i)
     {
         x = read(),y = read(),z = read();
         sum += z;
         add_edge(i,m+x,INF);//建立第i个人到中转站的边INF
         add_edge(i,m+y,INF);
         add_edge(s,i,z);//建立从S到第i个人的边，第i个人的获益
     }
     while (bfs())
         ans += dfs(s,INF);
     printf("%d",sum-ans);
     return ;
 }