Acdream 1171 Matrix Sum（上下界費用流建模）

Acdream 1171 Matrix Sum - 上下界費用流建模技巧

與 ACdream 1171 同題，這裡展示另一種建模思路：強制下界流滿流法。

核心思想：負費用強制滿流

不轉化為上界問題，而是直接在原圖添加輔助邊：

• 源點 → 行節點：兩條邊
  1. 容量 = Ki，費用 = -INF（強制優先跑滿）
  2. 容量 = INF，費用 = 0（額外流量）
• 列節點 → 匯點：同理兩條邊
• 行 → 列：容量 1，費用 = a[i][j]

跑最小費用流，當增廣路費用 ≥ 0 時停止（說明所有 -INF 邊已滿流）。答案 = 總費用 + INF × 總下界流量。

代碼實現（SPFA 版）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

#define ll int
#define INF 0x3f3f3f3f
#define N 105
#define M 1005

struct Edge { ll from, to, cap, cost, next; } edges[M<<1];
ll head[N], ecnt;
ll d[N], a[N], p[N]; bool inq[N];

void addEdge(ll u, ll v, ll cap, ll cost) {
    edges[ecnt] = {u, v, cap, cost, head[u]}; head[u] = ecnt++;
    edges[ecnt] = {v, u, 0, -cost, head[v]}; head[v] = ecnt++;
}

bool spfa(ll s, ll t, ll &flow, ll &cost) {
    fill(d, d+t+1, INF); memset(inq, 0, sizeof(inq));
    queue<ll> q; q.push(s); d[s]=0; a[s]=INF;
    while(!q.empty()) {
        ll u=q.front(); q.pop(); inq[u]=0;
        for(ll i=head[u]; ~i; i=edges[i].next) {
            Edge &e = edges[i];
            if(e.cap && d[e.to] > d[u] + e.cost) {
                d[e.to] = d[u] + e.cost; p[e.to]=i; a[e.to]=min(a[u], e.cap);
                if(!inq[e.to]) {inq[e.to]=1; q.push(e.to);}
            }
        }
    }
    if(d[t] > 0) return false;  // 費用非負，停止
    cost += d[t] * a[t]; flow += a[t];
    for(ll u=t; u!=s; u=edges[p[u]^1].to) {
        edges[p[u]].cap -= a[t]; edges[p[u]^1].cap += a[t];
    }
    return true;
}

ll minCost(ll s, ll t) {
    ll flow=0, cost=0;
    while(spfa(s,t,flow,cost));
    return cost;
}

int n, m, mp[55][55], R[55], C[55];
const int HINF = 100000;

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d", &mp[i][j]);
        for(int i=1;i<=n;i++) scanf("%d", &R[i]);
        for(int j=1;j<=m;j++) scanf("%d", &C[j]);
        
        memset(head, -1, sizeof(head)); ecnt=0;
        int S=0, T=n+m+1; ll lowerSum=0;
        
        for(int i=1;i<=n;i++) {
            lowerSum += R[i];
            addEdge(S, i, R[i], -HINF);  // 強制下界
            addEdge(S, i, INF, 0);       // 額外容量
        }
        for(int j=1;j<=m;j++) {
            lowerSum += C[j];
            addEdge(n+j, T, C[j], -HINF);
            addEdge(n+j, T, INF, 0);
        }
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
            addEdge(i, n+j, 1, mp[i][j]);
        
        printf("%d\n", minCost(S, T) + HINF * lowerSum);
    }
    return 0;
}

兩種建模對比

關鍵參數選擇

• HINF = 100000：需 > 最大可能總費用（50×50×10000 = 2.5e7），取 1e5 可能不夠，建議 1e9
• 費用類型用 long long 防溢出