本文共 2598 字，大约阅读时间需要 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/