解题思路

本题要求将N个模块分配到两个核心，使得总代价最小。总代价包括模块在核心的执行成本，以及不同核心间模块的数据交换额外成本。关键在于将问题转化为最小割模型，利用最大流算法求解：

核心转化思路：

1. 模型构建：将每个模块视为图中的节点，源点S代表核心1，汇点T代表核心2。
2. 边权定义：
   • 源点S到模块i连边，权值为模块i在核心1的执行成本Ai（选择核心1的代价）。
   • 模块i到汇点T连边，权值为模块i在核心2的执行成本Bi（选择核心2的代价）。
   • 对于每对模块(a,b)，连双向边，权值为数据交换成本w（若a和b分配到不同核心，需支付w，等价于割开这条边的代价）。
3. 最小割求解：最小割对应最小总代价，根据最大流最小割定理，通过计算S-T的最大流得到最小割值。

题意分析

问题本质：

• 输入：N个模块的双核心执行成本，M对模块间的跨核心数据交换成本。
• 输出：分配模块到两核心的最小总代价。

关键点：

1. 代价构成：
   • 模块在核心的执行成本（必选其一）。
   • 跨核心模块间的数据交换额外成本（若分配不同核心则产生）。
2. 图论模型：
   • 选核心1等价于节点属于S集合，选核心2等价于节点属于T集合。
   • 最小割即最小总代价：S-T割边的权值和为执行成本（S到节点或节点到T的边）与跨核心交换成本（a和b分属不同集合时的边）之和。

标程实现

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
const int MAXN = 20000 + 100;
const int MAXM = 1000000 + 10;
const int INF = 0x3f3f3f3f;

struct Edge {
    int from, to, cap, flow, next;
    Edge() {}
    Edge(int f, int t, int c, int fl, int n) : from(f), to(t), cap(c), flow(fl), next(n) {}
} edge[MAXM];
int head[MAXN], top;

void init() {
    memset(head, -1, sizeof(head));
    top = 0;
}

void addedge(int a, int b, int c) {
    edge[top] = Edge(a, b, c, 0, head[a]);
    head[a] = top++;
    edge[top] = Edge(b, a, 0, 0, head[b]);
    head[b] = top++;
}

int S, T, n, m;

void buildGraph() {
    S = 0;
    T = n + 1;
    for (int i = 1; i <= n; i++) {
        int A, B;
        scanf("%d%d", &A, &B);
        addedge(S, i, A);   // 选核心1的代价（割这条边则模块i去核心2）
        addedge(i, T, B);   // 选核心2的代价（割这条边则模块i去核心1）
    }
    while (m--) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        addedge(a, b, w);   // 跨核心交换代价（割这条边表示a和b在不同核心）
        addedge(b, a, w);
    }
}

int vis[MAXN], dis[MAXN], cur[MAXN];

bool bfs() {
    queue<int> q;
    memset(vis, 0, sizeof(vis));
    memset(dis, -1, sizeof(dis));
    q.push(S);
    vis[S] = 1;
    dis[S] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edge[i].next) {
            Edge& e = edge[i];
            if (!vis[e.to] && e.cap > e.flow) {
                vis[e.to] = 1;
                dis[e.to] = dis[u] + 1;
                if (e.to == T) return true;
                q.push(e.to);
            }
        }
    }
    return false;
}

int dfs(int u, int flow, int t) {
    if (u == t || flow == 0) return flow;
    int f, res = 0;
    for (int& i = cur[u]; i != -1; i = edge[i].next) {
        Edge& e = edge[i];
        if (dis[e.to] == dis[u] + 1 && (f = dfs(e.to, min(flow, e.cap - e.flow), t)) > 0) {
            e.flow += f;
            edge[i ^ 1].flow -= f;
            res += f;
            flow -= f;
            if (flow == 0) break;
        }
    }
    return res;
}

int maxFlow() {
    int flow = 0;
    while (bfs()) {
        memcpy(cur, head, sizeof(head));
        flow += dfs(S, INF, T);
    }
    return flow;
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        init();
        buildGraph();
        int minCost = maxFlow();
        printf("%d\n", minCost);
    }
    return 0;
}

代码解释

1. 图的构建：

   • 源点S连接所有模块，边权为核心1的执行成本；模块连接汇点T，边权为核心2的执行成本。
   • 每对模块间连双向边，权值为跨核心交换成本，确保若模块分属不同集合则产生该代价。

2. 最大流算法：

   • 使用Dinic算法求解最大流，通过BFS分层和DFS找增广路，时间复杂度为O(E√V)，适用于本题数据规模。
   • 最大流结果即最小割值，对应最小总代价。

3. 关键逻辑：

   • 割边的含义：S到模块的边被割表示模块选核心2，模块到T的边被割表示模块选核心1；模块间的边被割表示两者分属不同核心。
   • 最小割保证总代价最小，通过最大流算法高效求解。