題意
? ? ? 有n個(gè)顧客，m個(gè)供應(yīng)商，k種貨物，給你顧客對于每種貨物的要求個(gè)數(shù)，和供應(yīng)商對于每種貨物的現(xiàn)有量，以及供應(yīng)每種貨物的時(shí)候供應(yīng)商和顧客之間的運(yùn)輸單價(jià)，問你滿足所有顧客的前提下的最小運(yùn)輸費(fèi)用是多少。


思路：

? ? ? 滿足所有顧客的前提下的最小花費(fèi)，很容易就想到了費(fèi)用流，但是做這個(gè)題目有個(gè)小竅門，如果不想的話很可能把每個(gè)點(diǎn)拆成三個(gè)點(diǎn)，然后在去跑，但是這樣感覺寫著麻煩，AC肯定沒問題，但是仔細(xì)想想，每種貨物之間是沒有任何關(guān)系的，那么我們何不直接每種貨物都跑一遍費(fèi)用流，這樣寫起來很簡單，思路也清晰，建圖的話應(yīng)該不用說了吧，水建圖。

#include<stdio.h> #include<string.h> #include<queue>#define N 50 + 5 #define N_node 120 #define N_edge 6000 #define INF 100000000using namespace std;typedef struct {int from ,to ,next ,cost ,flow; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int s_x[N_node] ,mer[N_edge]; int need[N][N] ,supply[N][N];void add(int a ,int b ,int c ,int d) {E[++tot].from = a;E[tot].to = b;E[tot].cost = c;E[tot].flow = d;E[tot].next = list[a];list[a] = tot;E[++tot].from = b;E[tot].to = a;E[tot].cost = -c;E[tot].flow = 0;E[tot].next = list[b];list[b] = tot; }bool spfa(int s ,int t ,int n) {for(int i = 0 ;i <= n ;i ++)s_x[i] = INF;int mark[N_node] = {0};s_x[s] = 0 ,mark[s] = 1;queue<int>q;q.push(s);memset(mer ,255 ,sizeof(mer));while(!q.empty()){int xin ,tou = q.front();q.pop();mark[tou] = 0;for(int k = list[tou] ;k ;k = E[k].next){xin = E[k].to;if(s_x[xin] > s_x[tou] + E[k].cost && E[k].flow){s_x[xin] = s_x[tou] + E[k].cost;mer[xin] = k;if(!mark[xin]){mark[xin] = 1;q.push(xin);}}}}return mer[t] != -1; }int M_C_Flow(int s ,int t ,int n ,int sum) {int maxflow = 0 ,mincost = 0 ,minflow;while(spfa(s ,t ,n)){minflow = INF;for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])if(minflow > E[i].flow) minflow = E[i].flow;for(int i = mer[t] ;i + 1 ;i = mer[E[i].from]){E[i].flow -= minflow;E[i^1].flow += minflow;mincost += minflow * E[i].cost;}maxflow += minflow;}if(maxflow != sum) return -1;return mincost; }int main () {int n ,m ,k ,i ,j ,price;while(~scanf("%d %d %d" ,&n ,&m ,&k) && n + m + k){for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= k ;j ++)scanf("%d" ,&need[i][j]);for(i = 1 ;i <= m ;i ++)for(j = 1 ;j <= k ;j ++)scanf("%d" ,&supply[i][j]);int ans = 0 ,mk = 0;for(int ii = 1 ;ii <= k ;ii ++){memset(list ,0 ,sizeof(list)) ,tot = 1;for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m ;j ++){scanf("%d" ,&price);if(!price) continue;add(i ,j + n ,price ,INF);}if(mk) continue;int sum = 0;for(i = 1 ;i <= n ;i ++){add(0 ,i ,0 ,need[i][ii]);sum += need[i][ii];}for(i = 1 ;i <= m ;i ++)add(i + n ,n + m + 1 ,0 ,supply[i][ii]);int tmp = M_C_Flow(0 ,n + m + 1 ,n + m + 1 ,sum);if(tmp == -1) mk = 1;else ans += tmp;}mk ? puts("-1") : printf("%d\n" ,ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ 2516 基础费用流的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。