題干：

度度熊參與了喵哈哈村的商業(yè)大會，但是這次商業(yè)大會遇到了一個(gè)難題：?

喵哈哈村以及周圍的村莊可以看做是一共由n個(gè)片區(qū)，m條公路組成的地區(qū)。?

由于生產(chǎn)能力的區(qū)別，第i個(gè)片區(qū)能夠花費(fèi)a[i]元生產(chǎn)1個(gè)商品，但是最多生產(chǎn)b[i]個(gè)。?

同樣的，由于每個(gè)片區(qū)的購買能力的區(qū)別，第i個(gè)片區(qū)也能夠以c[i]的價(jià)格出售最多d[i]個(gè)物品。?

由于這些因素，度度熊覺得只有合理的調(diào)動物品，才能獲得最大的利益。?

據(jù)測算，每一個(gè)商品運(yùn)輸1公里，將會花費(fèi)1元。?

那么喵哈哈村最多能夠?qū)崿F(xiàn)多少盈利呢？?

Input

本題包含若干組測試數(shù)據(jù)。?
每組測試數(shù)據(jù)包含：?
第一行兩個(gè)整數(shù)n,m表示喵哈哈村由n個(gè)片區(qū)、m條街道。?
接下來n行，每行四個(gè)整數(shù)a[i],b[i],c[i],d[i]表示的第i個(gè)地區(qū)，能夠以a[i]的價(jià)格生產(chǎn)，最多生產(chǎn)b[i]個(gè)，以c[i]的價(jià)格出售，最多出售d[i]個(gè)。?
接下來m行，每行三個(gè)整數(shù),u[i],v[i],k[i]，表示該條公路連接u[i],v[i]兩個(gè)片區(qū)，距離為k[i]?

可能存在重邊，也可能存在自環(huán)。?

滿足:?
1<=n<=500,?
1<=m<=1000,?
1<=a[i],b[i],c[i],d[i],k[i]<=1000,?
1<=u[i],v[i]<=n?

Output

輸出最多能賺多少錢。?

Sample Input

2 1 5 5 6 1 3 5 7 7 1 2 1

Sample Output

23

題目大意：

? 給一張圖，求最小費(fèi)用。（不要求最大流，只要求在規(guī)定流量內(nèi)求出最小費(fèi)用）

解題報(bào)告：

從源點(diǎn)向每一地區(qū)i連邊，費(fèi)用為a[i]，流量為b[i]（代表地區(qū)i每生產(chǎn)一物品花費(fèi)）。

每一地區(qū)i向匯點(diǎn)連邊，費(fèi)用為-c[i]，流量為d[i]（代表地區(qū)i每賣出一物品所得）。

地區(qū)間兩兩連邊，費(fèi)用為地區(qū)間距離，流量為INF（代表每運(yùn)送一物品花費(fèi)）。

注意：若直接求則所求為最大流量條件下費(fèi)用（此時(shí)利潤不一定最大），所以當(dāng)增廣時(shí)發(fā)現(xiàn)費(fèi)用為正時(shí)直接退出增廣（此時(shí)繼續(xù)增加流量導(dǎo)致費(fèi)用變大，即繼續(xù)增加導(dǎo)致最終利潤減少）。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair #include <iomanip> using namespace std; const int MAX = 2e5 + 5; const int inf = 0x3f3f3f3f; struct node {int to,c,w,ne; } e[50005<<2]; int n,m; int head[MAX],d[MAX],vis[MAX],tot,p[MAX]; void add(int u,int v,int c,int cost=0) {e[++tot].to = v;e[tot].c = c;e[tot].w = cost;e[tot].ne = head[u];head[u] = tot;e[++tot].to = u;e[tot].c = 0; e[tot].w = -cost;e[tot].ne = head[v];head[v] = tot; } int N; bool bfs(int s,int t) {for(int i = 0; i<=N; i++) d[i]=inf,vis[i]=0;d[s]=0;queue<int>q;q.push(s);while(!q.empty()) {int u=q.front();q.pop();vis[u]=0;for(int i=head[u]; ~i; i=e[i].ne) {int j=e[i].to;if(e[i].c&&d[j]>d[u]+e[i].w) {d[j]=d[u]+e[i].w;p[j]=i;if(!vis[j])vis[j]=1,q.push(j);}}}return d[t]<=0; } int MCMF(int s,int t,int &flow) {ll ans=0;while(bfs(s,t)) {int x=t,f=inf;while(x!=s) {f = min(f,e[p[x]].c),x=e[p[x]^1].to;}flow += f;ans+=1LL*d[t]*f;x=t;while(x!=s) {e[p[x]].c-=f,e[p[x]^1].c+=f;x=e[p[x]^1].to;}}return ans; } int main() {while(~scanf("%d%d",&n,&m)) {int st=n+1,ed=st+1;N=ed;tot=1;memset(head,-1,sizeof(head));for(int a,b,c,d,i = 1; i<=n; i++) {scanf("%d%d%d%d",&a,&b,&c,&d);add(st,i,b,a);add(i,ed,d,-c);}int x,y,z;for(int i = 1; i<=m; i++) {scanf("%d%d%d",&x,&y,&z);add(x,y,inf,z);add(y,x,inf,z);}int ans2=0;int ans=MCMF(st,ed,ans2);printf("%d\n",-ans);}return 0 ; }

總結(jié)：

注意和最小費(fèi)用最大流的區(qū)別僅在spfa的時(shí)候返回值是<=0還是<INF?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【HDU - 6118】度度熊的交易计划（最小费用可行流，网络流费用流变形 ）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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