最大获利

【问题描述】
新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。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公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 - 投入成本之和）
【输入格式】
输入文件中第一行有两个正整数N和M 。
第二行中有N个整数描述每一个通讯中转站的建立成本，依次为P1, P2, …, PN 。
以下M行，第(i + 2)行的三个数Ai, Bi和Ci描述第i个用户群的信息。
所有变量的含义可以参见题目描述。
【输出格式】
你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。
【输入样例】
5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3
【输出样例】
4
【样例说明】
选择建立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。
QwQ，说是最大权闭合图的模板题，反正就是转换成最小割，再转换成最大流。

  1 #include <iostream>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <queue>
  6 const int inf = 1 << 30 , maxn = 57000 + 11 ; 
  7 using namespace std ;//1061109567
  8 int n , m , head[maxn] , cnt , dis[maxn] , s , t  , sum  , cur[maxn]  ; 
  9 queue < int > Q ;
 10 struct id
 11 {
 12     int nxt , to , val  ;
 13 } edge[500011] ;
 14 
 15 
 16 inline void Init ( )
 17 {
 18     freopen( "NSOOJ#10358.in" , "r" , stdin  ) ;
 19     freopen( "NSOOJ#10358.out" , "w" , stdout ) ;
 20 }
 21 
 22 int read( )
 23 {
 24     char ch = getchar( ) ; int k = 1 , ret = 0 ;
 25     while( ch < '0' || ch > '9' ) { if( ch == '-' ) k = -1 ; ch = getchar( ) ; }
 26     while( ch >= '0' && ch <= '9' ) ret = ret * 10 + ch - '0' , ch = getchar( ) ;
 27     return k * ret ;
 28 }
 29 
 30 void add( int u , int v , int va  )
 31 {
 32     edge[++cnt].nxt = head[u] , edge[cnt].to = v ;
 33     edge[cnt].val = va , head[u] = cnt ;
 34 }
 35 
 36 void input(  )
 37 {
 38     n = read( ) , m = read( ) ;
 39     s = 0 , t = n + m + 1  , cnt = -1 ;
 40     memset( head , -1 , sizeof(head) ) ;
 41     int a , b , c;
 42     for( int x = 1 ; x <= n ; ++x )
 43     {
 44         a = read( ) ;
 45         add( s , x , a ) ;
 46         add( x , s , 0 ) ;
 47     }
 48     for( int x = 1 ; x <= m ; ++x )
 49     {
 50         a = read( ) , b = read( ) , c = read( ) ;
 51         add( a , n + x , inf ) ; add( n + x , a , 0 ) ;
 52         add( b , n + x , inf ) ; add( n + x , b , 0 ) ;
 53         add( n + x , t , c ) ; add( t , n + x , 0 ) ;
 54         sum += c ;
 55     }
 56 }
 57 
 58 
 59 bool bfs(  )
 60 {
 61     memset( dis , -1 , sizeof(dis) ) ;
 62     dis[s] = 0  ; Q.push( s ) ;
 63     while( !Q.empty( ) )
 64     {
 65         int u = Q.front( ) ; Q.pop( ) ;
 66         for( int i = head[u] ; ~i ; i = edge[i].nxt )
 67         {
 68             int v = edge[i].to ;
 69             if( dis[v] < 0 && edge[i].val > 0 )
 70             {
 71                 dis[v] = dis[u] + 1 ;
 72                 Q.push( v ) ;
 73             }
 74         }      
 75     }
 76     return dis[t] != -1 ;
 77 }
 78 
 79 int dfs( int u , int f )
 80 {
 81     if( u == t ) return f ;
 82     int cost = 0 , ans  = 0 ;
 83     for( int i = cur[u] ; ~i ; i = edge[i].nxt )
 84     {
 85         int v = edge[i].to ;
 86         if( dis[v] != dis[u] + 1 ) continue ;
 87         ans = dfs( v , min( f-cost , edge[i].val ) ) ;
 88         edge[i].val -= ans , edge[i^1].val += ans , cost += ans ;
 89         if( edge[i].val ) cur[u] = i ;
 90         if( f == cost ) return f ;
 91     }
 92     if( !cost ) dis[u] = -1 ;
 93     return cost ;
 94 }
 95 
 96 
 97 
 98 void sov(  )
 99 {
100     int ans = 0 ;
101     while( bfs( ) )
102     {
103         for( int x = 0 ; x <= t ; x++ ) cur[x] = head[x] ;    
104         ans += dfs( s , inf ) ;
105     }
106     printf( "%d" , sum - ans ) ;
107 }
108 
109 
110 
111 int main( )
112 {
113 //    Init( ) ; 
114     input( ) ;
115     sov( ) ;
116 //    fclose( stdin ) ;
117 //    fclose( stdout ) ;
118     return 0 ;
119 }