hdu 3879 Base Station 最大权闭合图

  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\n",sum-dinic());
105     }
106     return 0;
107 }