[codevs 1789] 最大獲利（2006年NOI全國競賽）

[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,那麼ans=Total−MaxFlow;

代碼：

454ms 12MB

#include
#include
#include
#include
using namespace std;

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 edges;
  vector 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 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
, tot - isap.Maxflow(s, t, t+1));
    return 0;
}