hdu 3879 Base Stationの一番大きな権利は図を閉じます。

テーマリンク：http://acm.hdu.edu.cn/showproblem.php?pid=3879
A famous mobile communication company is planing to build a new set of base stations.Acctording to the previous investigation，n place the possible new locations to build those new stations.However，divance ofso the costt to built a station at different placces are different.The cost to build a new station the ith place is Pi(1==i==n)
When compleete building、two plces which both have stations can communicate with each other.
Besides、according to the marketting department、the company has received m requirements.The ith requirement is represented by three integers Ai、Bi and Ci、which means flance Ai and Bi Bi Bi Bi Bi communication the communication protement
Now，the company wants to maximize the profits，so maybonts just part of the possible locations will be cheen to build new stations.The boss wants to know the maximum profits.
 
都市iに新しい駅を作る費用はPiで、二つの都市に駅があると互いに通信し合うことができ、会社が利益を得ることができます。例えば、A都市とB都市が互いに通信するなら、Cの利益を得ることができます。最大の利益はいくらですか？
アルゴリズム解析：最大のクローズドマップ。二つの都市が互いに通信しているこの辺を点として、例えばA B C、AとBのこの辺を点Uとし、辺fromからUまで、右側をCとし、側UからA、UからBまでの値を無限大とし、辺Aからto、Bからtoまで、権値はこの都市に宿場を作る費用である。

  1 #include<iostream>

  2 #include<cstdio>

  3 #include<cstring>

  4 #include<cstdlib>

  5 #include<cmath>

  6 #include<algorithm>

  7 #include<queue>

  8 #define inf 0x7fffffff

  9 using namespace std;

 10 const int maxn=55000+10;

 11 const int M = 25000000+10;

 12 

 13 int n,m,from,to;

 14 struct node

 15 {

 16     int v,flow;

 17     int next;

 18 }edge[M*2];

 19 int head[maxn],edgenum;

 20 

 21 void add(int u,int v,int flow)

 22 {

 23     edge[edgenum].v=v ;edge[edgenum].flow=flow;

 24     edge[edgenum].next=head[u] ;head[u]=edgenum++ ;

 25 

 26     edge[edgenum].v=u ;edge[edgenum].flow=0;

 27     edge[edgenum].next=head[v] ;head[v]=edgenum++ ;

 28 }

 29 

 30 int d[maxn];

 31 int bfs()

 32 {

 33     memset(d,0,sizeof(d));

 34     d[from]=1;

 35     queue<int> Q;

 36     Q.push(from);

 37     while (!Q.empty())

 38     {

 39         int u=Q.front() ;Q.pop() ;

 40         for (int i=head[u] ;i!=-1 ;i=edge[i].next)

 41         {

 42             int v=edge[i].v;

 43             if (!d[v] && edge[i].flow)

 44             {

 45                 d[v]=d[u]+1;

 46                 Q.push(v);

 47                 if (v==to) return 1;

 48             }

 49         }

 50     }

 51     return 0;

 52 }

 53 

 54 int dfs(int u,int flow)

 55 {

 56     if (u==to || flow==0) return flow;

 57     int cap=flow;

 58     for (int i=head[u] ;i!=-1 ;i=edge[i].next)

 59     {

 60         int v=edge[i].v;

 61         if (d[v]==d[u]+1 && edge[i].flow)

 62         {

 63             int x=dfs(v,min(edge[i].flow,cap));

 64             edge[i].flow -= x;

 65             edge[i^1].flow += x;

 66             cap -= x;

 67             if (cap==0) return flow;

 68         }

 69     }

 70     return flow-cap;

 71 }

 72 

 73 int dinic()

 74 {

 75     int sum=0;

 76     while (bfs()) sum += dfs(from,inf);

 77     return sum;

 78 }

 79 

 80 int an[maxn];

 81 int main()

 82 {

 83     while (scanf("%d%d",&n,&m)!=EOF)

 84     {

 85         memset(head,-1,sizeof(head));

 86         edgenum=0;

 87         from=n+m+1;

 88         to=from+1;

 89         for (int i=1 ;i<=n ;i++)

 90         {

 91             scanf("%d",&an[i]);

 92             add(i,to,an[i]);

 93         }

 94         int a,b,c;

 95         int sum=0;

 96         for (int i=1 ;i<=m ;i++)

 97         {

 98             scanf("%d%d%d",&a,&b,&c);

 99             sum += c;

100             add(from,n+i,c);

101             add(n+i,a,inf);

102             add(n+i,b,inf);

103         }

104         printf("%d
",sum-dinic());

105     }

106     return 0;

107 }