1 条题解

  • 0
    @ 2025-4-9 21:10:31

    题意分析

    NN个供应商,MM个店主,KK种物品。每个供应商对每种物品的的供应量已知,每个店主对每种物品的需求量的已知,从不同的供应商运送不同的货物到不同的店主手上需要不同的花费,又已知从供应商送第几种货物的单位数量到店主手上所需的单位花费。 问:供应是否满足需求?如果满足,最小运费是多少?

    解题思路

    一开始是把所有商家的每种物品和所有供应商所有物品连边跑费用流,但很麻烦,因为这样建出来的图,边数会非常的庞大。那么其实转化一下思路,每种物品之间是不会互相影响的,那么把每种物品求出来后,累加起来就是答案了。

    C++实现

    cpp

    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <algorithm>
    using namespace std;
     
    const int MAXNODE = 5005;
    const int MAXEDGE = 500005;
    typedef int Type;
    const Type INF = 0x3f3f3f3f;
     
    struct Edge {
    	int u, v;
    	Type cap, flow, cost;
    	Edge() {}
    	Edge(int u, int v, Type cap, Type flow, Type cost) {
    		this->u = u;
    		this->v = v;
    		this->cap = cap;
    		this->flow = flow;
    		this->cost = cost;
    	}
    };
     
    struct MCFC {
    	int n, m, s, t;
    	Edge edges[MAXEDGE];
    	int first[MAXNODE];
    	int next[MAXEDGE];
    	int inq[MAXNODE];
    	Type d[MAXNODE];
    	int p[MAXNODE];
    	Type a[MAXNODE];
     
    	void init(int n) {
    		this->n = n;
    		memset(first, -1, sizeof(first));
    		m = 0;
    	}
     
    	void add_Edge(int u, int v, Type cap, Type cost) {
    		edges[m] = Edge(u, v, cap, 0, cost);
    		next[m] = first[u];
    		first[u] = m++;
    		edges[m] = Edge(v, u, 0, 0, -cost);
    		next[m] = first[v];
    		first[v] = m++;
    	}
     
    	bool bellmanford(int s, int t, Type &flow, Type &cost) {
     
    		for (int i = 0; i < n; i++) d[i] = INF;
    		memset(inq, false, sizeof(inq));
    		d[s] = 0; inq[s] = true; p[s] = s; a[s] = INF;
    		queue<int> Q;
    		Q.push(s);
    		while (!Q.empty()) {
    			int u = Q.front(); Q.pop();
    			inq[u] = false;
    			for (int i = first[u]; i != -1; i = next[i]) {
    				Edge& e = edges[i];
    				if (e.cap > e.flow && d[e.v] > d[u] + e.cost) {
    					d[e.v] = d[u] + e.cost;
    					p[e.v] = i;
    					a[e.v] = min(a[u], e.cap - e.flow);
    					if (!inq[e.v]) {Q.push(e.v); inq[e.v] = true;}
    				}
    			}
    		}
    		if (d[t] == INF) return false;
    		flow += a[t];
    		cost += d[t] * a[t];
    		int u = t;
    		while (u != s) {
    			edges[p[u]].flow += a[t];
    			edges[p[u]^1].flow -= a[t];
    			u = edges[p[u]].u;
    		}
    		return true;
    	}
     
    	Type Mincost(int s, int t, Type sum) {
    		Type flow = 0, cost = 0;
    		while (bellmanford(s, t, flow, cost));
    		if (sum != flow) cost = -1;
    		return cost;
    	}
    } gao;
     
    const int N = 55;
     
    int n, m, k, sum;
    int a[N][N], b[N][N];
     
    int solve() {
    	int c, ans = 0, flag = 0;
    	for (int i = 0; i < k; i++) {
    		gao.init(n + m + 2);
    		for (int j = 1; j <= m; j++)
    			gao.add_Edge(0, j, b[j][i], 0);
    		int sum = 0;
    		for (int j = 1; j <= n; j++) {
    			sum += a[j][i];
    			gao.add_Edge(m + j, n + m + 1, a[j][i], 0);
    		}
    		for (int x = 1; x <= n; x++) {
    			for (int y = 1; y <= m; y++) {
    				scanf("%d", &c);
    				gao.add_Edge(y, x + m, INF, c);
    			}
    		}
    		if (flag) continue;
    		int tmp = gao.Mincost(0, n + m + 1, sum);
    		if (tmp == -1) flag = 1;
    		else ans += tmp;
    	}
    	if (flag) ans = -1;
    	return ans;
    }
     
    int main() {
    	while (~scanf("%d%d%d", &n, &m, &k) && n) {
    		for (int i = 1; i <= n; i++)
    			for (int j = 0; j < k; j++)
    				scanf("%d", &a[i][j]);
    		for (int i = 1; i <= m; i++)
    			for (int j = 0; j < k; j++)
    				scanf("%d", &b[i][j]);
    		printf("%d\n", solve());
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    3047
    时间
    1000ms
    内存
    256MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者