hdu 3879 Base Station bzoj 1497 最大获利问题最大权闭合子图

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3879

http://www.lydsy.com/JudgeOnline/problem.php?id=1497

题意：

在前期市场调查和站址勘测之后，公司得到了一共N个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第i个通讯中转站需要的成本为Pi（1≤i≤N）。另外公司调查得出了所有期望中的用户群，一共M个。关于第i个用户群的信息概括为Ai, Bi和Ci：这些用户会使用中转站Ai和中转站Bi进行通讯，公司可以获益Ci。（1≤i≤M, 1≤Ai, Bi≤N） THU集团的CS&T公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 - 投入成本之和）

思路：

经典的最大权闭合子图问题。

因为用户通过使用中转站Ai和中转站Bi进行通讯，公司可以获益Ci。即满足这个用户群，就可以得到收益c。

但是获得收益C需要一个必要条件：建立中转站a和b，需要花去一定的费用，这就是满足了闭合图的性质。

所以按照最大权闭合子图的方法来建图。

建立超级源点s和超级汇点t。

s向每个收益点连一条边，容量为ci。

每个站点向t连一条边，容量为pi。

每个需要a, b, i中 i分别向a和b连一条边，容量为inf。

然后求最小割。

答案就是正权点总权和 - 最小割。

  1 //#include <bits/stdc++.h>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <vector>
  6 #include <queue>
  7 using namespace std;
  8 struct Edge
  9 {
 10     int from, to, cap, flow;
 11     Edge(int f, int t, int c, int fl)
 12     {
 13         from = f; to = t; cap = c; flow = fl;
 14     }
 15 };
 16 #define maxn 55010
 17 #define inf 0x3f3f3f3f
 18 vector <Edge> edges;
 19 int n, m, s, t;
 20 vector <int> G[maxn];
 21 int d[maxn], vis[maxn], cur[maxn];
 22 void AddEdge(int from, int to, int cap)
 23 {
 24     edges.push_back(Edge(from, to, cap, 0));
 25     edges.push_back(Edge(to, from, 0, 0));
 26     m = edges.size();
 27     G[from].push_back(m-2);
 28     G[to].push_back(m-1);
 29 }
 30 bool bfs()
 31 {
 32     memset(vis, 0, sizeof(vis));
 33     d[s] = 0; vis[s] = 1;
 34     queue <int> q; q.push(s);
 35     while(!q.empty())
 36     {
 37         int x = q.front(); q.pop();
 38         for(int i = 0; i < G[x].size(); i++)
 39         {
 40             Edge &e = edges[G[x][i]];
 41             if(!vis[e.to] && e.cap > e.flow)
 42             {
 43                 vis[e.to] = 1;
 44                 d[e.to] = d[x] + 1;
 45                 q.push(e.to);
 46             }
 47         }
 48     }
 49     return vis[t];
 50 }
 51 int dfs(int x, int a)
 52 {
 53     if(x == t || a == 0) return a;
 54     int flow = 0, f;
 55     for(int &i = cur[x]; i < G[x].size(); i++)
 56     {
 57         Edge &e = edges[G[x][i]];
 58         if(d[e.to] == d[x]+1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0)
 59         {
 60             e.flow += f;
 61             edges[G[x][i]^1].flow -= f;
 62             flow += f;
 63             a -= f;
 64             if(a == 0) break;
 65         }
 66     }
 67     return flow;
 68 }
 69 int maxflow()
 70 {
 71     int flow = 0;
 72     while(bfs())
 73     {
 74         memset(cur, 0, sizeof(cur));
 75         flow += dfs(s, inf);
 76     }
 77     return flow;
 78 }
 79 int N, M;
 80 int p[5050];
 81 int main() 
 82 {
 83     //freopen("in.txt", "r", stdin);
 84     //freopen("out.txt", "w", stdout);
 85     while(~scanf("%d%d", &N, &M))
 86     {
 87         edges.clear();
 88         s = 0; t = N+M+1; n = N+M+2;
 89         for(int i = 0; i <= t; i++) G[i].clear();
 90         for(int i = 1; i <= N; i++)
 91         {
 92             scanf("%d", &p[i]);
 93             AddEdge(i+M, t, p[i]);
 94         }
 95         int sum = 0;
 96         for(int i = 1; i <= M; i++)
 97         {
 98             int a, b, c;
 99             scanf("%d%d%d", &a, &b, &c);
100             sum += c;
101             AddEdge(s, i, c);
102             AddEdge(i, a+M, inf);
103             AddEdge(i, b+M, inf);
104         }
105         int flow = maxflow();
106         printf("%d
", sum-flow);
107         
108     }
109     return 0;
110 }

hdu 3879 Base Station bzoj 1497 最大获利问题 最大权闭合子图

hdu 3879 Base Station bzoj 1497 最大获利问题最大权闭合子图