設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置： 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

POJ 1087 A Plug for UNIX：最大流建模适配器链

     編輯：關於C++

题目大意

n 个插座，m 个设备，k 种适配器（无限量）。适配器将一种插头转为另一种插座。求最少有多少设备无法插上。

最大流建模

  • 源点 S → 每个插座（容量 1）
  • 每个设备 → 汇点 T（容量 1）
  • 插座类型 → 设备插头类型：若类型匹配，容量 1
  • 适配器 b→a（插座 a，插头 b）：类型 b → 类型 a，容量 INF（可级联）
  • 最大流 = 可满足设备数，答案 = m - 最大流

Dinic 算法实现

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

const int MAXN = 1000, INF = 0x3f3f3f3f;
int mp[MAXN][MAXN], level[MAXN];
map id;
int N, S, T;

bool bfs() {
    memset(level, -1, sizeof(level));
    queue q; q.push(S); level[S] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v=0; v 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                q.push(v);
            }
    }
    return level[T] != -1;
}

int dfs(int u, int f) {
    if (u == T) return f;
    int used = 0;
    for (int v=0; v 0 && level[v] == level[u]+1) {
            int w = dfs(v, min(f-used, mp[u][v]));
            mp[u][v] -= w; mp[v][u] += w;
            used += w;
            if (used == f) return used;
        }
    if (!used) level[u] = -1;
    return used;
}

int dinic() {
    int flow = 0;
    while (bfs()) flow += dfs(S, INF);
    return flow;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        id.clear(); memset(mp, 0, sizeof(mp));
        int cnt = 1; S = 0; T = 500;
        // 插座
        for (int i=0;i


关键建模细节


    

  1. 字符串映射：用 map 给每种类型编号
    2. 

  2. 适配器方向：输入「插座类型 插头类型」→ 边 插头类型 → 插座类型
    3. 

  3. 无限容量：适配器可级联，用 INF 表示
    4. 

  4. 多源多汇：超级源连插座，设备连超级汇
    5. 




复杂度


    

  • 节点 ≤ 100+100+100×2 ≈ 400
    • 

  • Dinic O(E√V) 极快
    •
  1. 上一篇文章：
  2. 下一篇文章：
關於C++
C++ 數據持久化方案：無數據庫場景下的文件存儲與 JSON 實戰 C++ 數據持久化方案：無數據庫場景下的文件存儲與 JSON 實戰

前言：初學者也能實現數據落地 數據持久化是程序的核心能力。對
POJ 3070 Fibonacci：矩陣快速冪求第 N 項模 10000 POJ 3070 Fibonacci：矩陣快速冪求第 N 項模 10000

POJ 3070 Fibonacci 完整解析 求第 N 個
ZOJ 1037 / HDU 1046 Gridland：找規律的幾何最短路徑 ZOJ 1037 / HDU 1046 Gridland：找規律的幾何最短路徑

題目大意 在 n × m 的網格中，從左上角 (1,1) 出
經典算法：字符串所有組合的遞歸生成 經典算法：字符串所有組合的遞歸生成

問題描述 給定一個字符串，輸出其所有非空子集（組合），即從中
Delphi TList 物件指標清單類別完整操作指南 C++Builder 登錄檔操作：遞迴列舉子鍵與值的完整範例 VC 文件目錄操作大全：存在性判斷、創建、大小獲取、遞歸枚舉與 STL 封裝 C++11 左值引用與右值引用完整指南：語法、語義與移動構造 Windows 繪圖核心：WM_PAINT、BeginPaint/EndPaint 與無效區域機制全解析 LeetCode 199 Binary Tree Right Side View：層序遍歷取最右節點 C++ 類與繼承實戰演練：賬戶體系、多重繼承構造順序、菱形問題
欄目導航
  • C++ 基礎
  • C++ 入門
  • 關於C++
    • Copyright © 程式碼之家 All Rights Reserved