[codevs 1789] 最大获利（2006年NOI全国竞赛）

描述：

题解：

第一次写最大闭合子图的题，把过程写详细。

如果要选择第i个用户群，那么就必须选择中转站ai和bi。而这个约束条件是最大闭合子图的经典条件，先来看看最大闭合子图的定义：

最大权闭合子图即为，给定一个图，每个点有一个权值，有正有负。有一些有向边(i,j)，表示若选了点i，那么也必须选点j。请求出一个合法点集使得点权和尽量大.

然后开始建模： 首先建立二分图，建立附加源s和附加汇t，从s到每个用户群连一条容量为ci的边，，表示选择这个用户群的收益；从每个中转站到t连一条容量为pi的边，表示中转站的成本，注意这个成本其实是负数，这里取相反数即正值，后面要转化。再从用户群到需要的中转站连一条容量为INF的边。求s到t的最大流，用户群的权值和-最大流量就是最终结果。

分析： 最大流一定对应一个最小割，那么考虑这样一组边：s->ci->ai、bi->t，其中有且只有一条边在最小割中【1】，且只能为s->ai(bi)和ci->t中的一条【2】，因为最小割的性质得出【1】，而用户群和中转站之间的边容量已经被设为INF，不会满流得出【2】。

假设所有用户群都选择并且不需要任何中转站，此时获利为Total。然后我们让割集的流量代表相对Total损失的钱。损失的钱包括两部分：1.放弃选择的用户群所带来的收益；2.选择一些必要的中转站需要的成本。

如果s->ci在最小割中，代表损失掉ci的钱，那么就没有选择ci这个中转站。对相应ai和bi没有影响。 相反的，如果s->ci不在最小割中，则代表选择ci这个中转站（因为不损失ci的获利），那么相应ai、bi->t的边一定在最小割中，代表选择ai和bi（损失这些成本）。这样就满足了选择ci，ai、bi一定被选。

最后要让损失的钱最少，也就是割的流量最小，最小割流量对应着最大流MaxFlow,那么

代码：

454ms 12MB

;const int maxn = 5000 + 10;const int maxnode = 50000 + 5000 + 10;const int INF = 1e9 + 7;struct Edge { int from, to, cap, flow;};struct ISAP { int n, m, s, t; vector<Edge> edges; vector<int> G[maxnode]; bool vis[maxnode]; int d[maxnode], cur[maxnode], p[maxnode], num[maxnode];void AddEdge(int from, int to, int cap) {edges.push_back((Edge){from, to, cap, 0});edges.push_back((Edge){to, from, 0, 0});m = edges.size();G[from].push_back(m-2);G[to].push_back(m-1); } bool BFS() {memset(vis, 0, sizeof(vis));queue<int> Q;Q.push(t);vis[t] = 1;d[t] = 0;while(!Q.empty()) {int x = Q.front(); Q.pop();for(int i = 0; i < G[x].size(); i++) {Edge& e = edges[G[x][i]^1];if(!vis[e.from] && e.cap > e.flow) {vis[e.from] = 1;d[e.from] = d[x] + 1;Q.push(e.from);}}}return vis[s]; } int Augment() {int x = t, a = INF;while(x != s) {Edge& e = edges[p[x]];a = min(a, e.cap-e.flow);x = edges[p[x]].from;}x = t;while(x != s) {edges[p[x]].flow += a;edges[p[x]^1].flow -= a;x = edges[p[x]].from;}return a; } int Maxflow(int s, int t, int n) {this->s = s; this->t = t; this->n = n;int flow = 0;BFS();memset(num, 0, sizeof(num));for(int i = 0; i < n; i++) num[d[i]]++;int x = s;memset(cur, 0, sizeof(cur));while(d[s] < n) {if(x == t) {flow += Augment();x = s;}int ok = 0;for(int i = cur[x]; i < G[x].size(); i++) {Edge& e = edges[G[x][i]];if(e.cap > e.flow && d[x] == d[e.to] + 1) {ok = 1;p[e.to] = G[x][i];cur[x] = i;x = e.to;break;}}if(!ok) {int m = n-1;for(int i = 0; i < G[x].size(); i++) {Edge& e = edges[G[x][i]];if(e.cap > e.flow) m = min(m, d[e.to]);}if(–num[d[x]] == 0) break;num[d[x] = m+1]++;cur[x] = 0;if(x != s) x = edges[p[x]].from;}}return flow; }}isap;int p[maxn];int main() {int n, m, s, t;scanf(“%d%d”, &n, &m);s = 0; t = m + n + 1;for(int i = m + 1; i <= m + n; i++) {int p;scanf(“%d”, &p);isap.AddEdge(i, t, p);}int tot = 0;for(int i = 1; i <= m; i++) {int a, b, c;scanf(“%d%d%d”, &a, &b, &c);tot += c;isap.AddEdge(s, i, c);isap.AddEdge(i, a + m, INF);isap.AddEdge(i, b + m, INF);}printf(“%d\n”, tot – isap.Maxflow(s, t, t+1));return 0;}

午餐，晚餐。或许吃得不好，可是却依旧为对方擦去嘴角的油渍。