您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 4975 高斯消元與網絡流：矩陣可行性判定的最大流建模

編輯：C++ 入門

HDU 4975：從高斯消元到最大流的矩陣構造問題

題意：給定 n 行 m 列矩陣，每行和 aᵢ、每列和 bⱼ 已知。每個元素取值 0~9。判斷是否存在滿足條件的矩陣，若存在進一步判斷解是否唯一（「So simple!」）、多解（「So young!」）或無解（「So naive!」）。

建模為最大流問題

源點 S → 每行節點 i，容量 aᵢ。
每行 i → 每列 j，容量 9（元素上限）。
每列 j → 匯點 T，容量 bⱼ。
最大流 = Σaᵢ = Σbⱼ 則可行，否則無解。

唯一性判定：環檢測

若存在多解，則殘量網絡中存在環（可沿環增減流量）。具體檢測：對每個非飽和邊 (i,j)（流量 < 9），構建有向圖：
若 flow[i][j] > 0 有向邊 j → i（可減流）；
若 flow[i][j] < 9 有向邊 i → j（可增流）。
若此圖有環 → 多解（「So young!」），否則唯一解（「So simple!」）。

優化：矩陣 DP + 剪枝判環

作者提到比賽時用判環 TLE，後改用矩陣 DP 剪枝通過。核心思想：利用行列和約束的傳遞性，快速排除不可能的賦值組合，減少流網絡規模或直接構造解。

完整 ISAP 最大流 + 判環代碼（C++）

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
struct Edge { int v, cap, next; } e[1000000];
int head[MAXN], cnt, S, T, NV;
int cur[MAXN], dis[MAXN], gap[MAXN], pre[MAXN];

void addEdge(int u, int v, int cap) {
    e[cnt] = {v, cap, head[u]}; head[u] = cnt++;
    e[cnt] = {u, 0, head[v]}; head[v] = cnt++;
}

void bfs() {
    memset(dis, -1, sizeof(dis));
    memset(gap, 0, sizeof(gap));
    queue q; q.push(T); dis[T]=0; gap[0]=1;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(int i=head[u]; i!=-1; i=e[i].next) {
            int v=e[i].v;
            if(dis[v]==-1 && e[i^1].cap>0) {
                dis[v]=dis[u]+1; gap[dis[v]]++; q.push(v);
            }
        }
    }
}

int isap() {
    memcpy(cur, head, sizeof(head));
    int flow=0, u=S; pre[S]=S;
    bfs();
    while(dis[S] < NV) {
        if(u==T) {
            int f=INF, pos=S;
            for(int i=S; i!=T; i=e[cur[i]].v)
                if(e[cur[i]].cap < f) f=e[cur[i]].cap, pos=i;
            for(int i=S; i!=T; i=e[cur[i]].v) {
                e[cur[i]].cap -= f; e[cur[i]^1].cap += f;
            }
            flow += f; u=pos;
        }
        bool advanced=false;
        for(int i=cur[u]; i!=-1; i=e[i].next)
            if(e[i].cap>0 && dis[u]==dis[e[i].v]+1) {
                cur[u]=i; pre[e[i].v]=u; u=e[i].v; advanced=true; break;
            }
        if(!advanced) {
            if(--gap[dis[u]]==0) break;
            int mind=NV;
            for(int i=head[u]; i!=-1; i=e[i].next)
                if(e[i].cap>0) mind=min(mind, dis[e[i].v]);
            dis[u]=mind+1; gap[dis[u]]++;
            u=pre[u];
        }
    }
    return flow;
}

bool hasCycle(int n, int m, int flow[][600]) {
    // 構建有向圖檢測環：flow[i][j]>0 加邊 j->i；flow[i][j]<9 加邊 i->j
    // 用 DFS 或拓撲排序檢測環
    // 代碼略...
    return false;
}

int main() {
    int T; scanf("%d", &T);
    for(int cas=1; cas<=T; cas++) {
        int n,m; scanf("%d%d", &n,&m);
        vector a(n+1), b(m+1);
        long long sumA=0, sumB=0;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]), sumA+=a[i];
        for(int j=1;j<=m;j++) scanf("%d",&b[j]), sumB+=b[j];
        printf("Case #%d: ", cas);
        if(sumA!=sumB) { puts("So naive!"); continue; }
        // 建圖、跑流、判環...
        // 完整代碼較長，核心邏輯如上
    }
    return 0;
}