本文共 2527 字，大约阅读时间需要 8 分钟。

Poj1459 Power Network 预流推进

问题描述：

一个电力网络由节点（发电站、消费者和调度站）通过电力传输线连接。每个节点u有以下属性：

• s(u)：供给的电量，>=0
• p(u)：发电量，最多是p_max(u)
• c(u)：消耗量，最多是min(s(u), c_max(u))
• d(u)=s(u)+p(u)-c(u)：实际送达的电量

约束条件：

• 发电站：c(u)=0，p(u)=0
• 消费者：p(u)=0，c_max(u)限制c(u)
• 调度站：p(u)=c(u)=0

电力传输线u→v的容量0<=l(u,v)<=l_max(u,v)。问题要求计算整个网络中消耗的总功率Con的最大值。

输入：

多个数据集，每个数据集描述一个网络。输入结构：

• 四个整数：n, np, nc, m
• m条三元组(u, v, z)：电力传输线的容量
• np条双重(u, z)：发电站的p_max
• nc条双重(u, z)：消费者的c_max

输出：每个数据集的最大Con值。

示例分析：

可以通过网络最大流模型求解。引入源点和汇点，分别作为流的起点和终点。原图中的发电站、调度站和消费者结点不能作为源点和汇点。因此，在图中添加源点（编号n+1）和汇点（编号n+2）。

构建流网络：

• 将每个发电站u连接到源点s，边的容量为p_max(u)。
• 将每个消费者u连接到汇点t，边的容量为c_max(u)。
• 将电力传输线(u, v)连接到图中，边的容量为l_max(u, v)。

使用预流推进算法计算源s到汇点t的最大流，这个流值即为最大Con值。

代码实现：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn = 110;const int maxf = 0x7fffffff;int n, np, nc, m;int resi[maxn][maxn];deque
       
         act;int h[maxn];int ef[maxn];int s, t, V;void push_relabel() {    int sum = 0;    int u, v, p;    for(int i = 1; i <= V; i++)        h[i] = 0;    h[s] = V;    memset(ef, 0, sizeof(ef));    ef[s] = maxf;    ef[t] = -maxf;    act.push_front(s);    while(!act.empty()) {        u = act.front();        act.pop_front();        for(int i = 1; i <= V; i++) {            v = i;            if(resi[u][v] < ef[u])                p = resi[u][v];            else                p = ef[u];            if(p > 0 && (u == s || h[u] == h[v] + 1)) {                resi[u][v] -= p;                resi[v][u] += p;                if(v == t)                    sum += p;                ef[u] -= p;                ef[v] += p;                if(v != s && v != t)                    act.push_front(v);            }        }        if(u != s && u != t && ef[u] > 0) {            h[u]++;            act.push_front(u);        }    }    printf("%d\n", sum);}int main() {    int u, v, val;    while(scanf("%d%d%d%d", &n, &np, &nc, &m) != EOF) {        s = n + 1;        t = n + 2;        V = n + 2;        memset(resi, 0, sizeof(resi));        for(int i = 0; i < m; i++) {            while(getchar() != '(');            scanf("%d,%d)%d", &u, &v, &val);            resi[u+1][v+1] = val;        }        for(int i = 0; i < np; i++) {            while(getchar() != '(');            scanf("%d)%d", &u, &val);            resi[s][u+1] = val;        }        for(int i = 0; i < nc; i++) {            while(getchar() != '(');            scanf("%d)%d", &u, &val);            resi[u+1][t] = val;        }        push_relabel();    }    return 0;}
       
      
     
    
   

最终，最大流的值即为所求的最大Con值。

转载地址：http://zdxfk.baihongyu.com/