度度熊的交易計劃
Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1074 Accepted Submission(s): 389
Problem Description 度度熊參與了喵哈哈村的商業大會,但是這次商業大會遇到了一個難題:
喵哈哈村以及周圍的村莊可以看做是一共由n個片區,m條公路組成的地區。
由于生産能力的差別,第i個片區能夠花費a[i]元生産1個商品,但是最多生産b[i]個。
同樣的,由于每個片區的購買能力的差別,第i個片區也能夠以c[i]的價格出售最多d[i]個物品。
由于這些因素,度度熊覺得隻有合理的調動物品,才能獲得最大的利益。
據測算,每一個商品運輸1公裡,将會花費1元。
那麼喵哈哈村最多能夠實作多少盈利呢?
Input 本題包含若幹組測試資料。
每組測試資料包含:
第一行兩個整數n,m表示喵哈哈村由n個片區、m條街道。
接下來n行,每行四個整數a[i],b[i],c[i],d[i]表示的第i個地區,能夠以a[i]的價格生産,最多生産b[i]個,以c[i]的價格出售,最多出售d[i]個。
接下來m行,每行三個整數,u[i],v[i],k[i],表示該條公路連接配接u[i],v[i]兩個片區,距離為k[i]
可能存在重邊,也可能存在自環。
滿足:
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
Source 2017"百度之星"程式設計大賽 - 初賽(B)
Recommend liuyiding | We have carefully selected several similar problems for you: 6132 6131 6130 6129 6128
思路:
最最最裸的最小費用流把,注意是最小費用流, 這題不比要求最大流,隻要費用最高就好了, 那麼就把spfa裡改成 if(dis[t] > 0) return 0; else return 1;就好了...
①建立源點,連入各個節點,花費為-c【i】,流為d【i】。 (如果是最小利益,就要正常建, 花費是負的,收益是正的)
②建立彙點,将各個節點連入彙點,花費為a【i】,流為b【i】。
③将圖的邊(u,v)加到網絡中,花費為w,流為INF。
然後連續最短路跑費用流就行了,值得注意的一個坑點是,我們如果從源點到彙點的距離大于0的時候,我們這條邊如果走過去了就相當于賠錢了。
是以當dis【tt】>0的時候,我們終止跑費用流。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;
const int maxn = 5e2 + 7;
const int maxe = 200005;
const int INF = 0x3f3f3f3f;
int head[maxe], dis[maxn], path[maxn], pre[maxn], book[maxn] , n, m, s, t, k, sum;
struct node
{
int v, w, f, next, cnt;
}edge[maxe];
void addEdge(int u, int v, int f, int w)
{
edge[k].v = v;
edge[k].w = w;
edge[k].f = f;
edge[k].cnt = k;
edge[k].next = head[u];
head[u] = k++;
edge[k].v = u;
edge[k].w = -w;
edge[k].f = 0;
edge[k].cnt = k;
edge[k].next = head[v];
head[v] = k++;
}
void init()
{
s = 0, t = n+1, k = 0;
memset(head, -1, sizeof(head));
}
int spfa()
{
queue<int> q;
q.push(s);
memset(pre, -1, sizeof(pre));
memset(path, -1, sizeof(path));
for(int i = 1; i <= t; i++) dis[i] = INF;
dis[s] = 0;
memset(book, 0, sizeof(book));
book[s] = 1;
while(!q.empty())
{
int u = q.front();
q.pop();
book[u] = 0;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int to = edge[i].v;
int w = edge[i].w;
int f = edge[i].f;
if(f && dis[to] > dis[u] + w)
{
dis[to] = dis[u] + w;
pre[to] = u;
path[to] = edge[i].cnt;
if(!book[to])
{
q.push(to);
book[to] = 1;
}
}
}
}
if(dis[t] > 0) return 0;
else return 1;
}
int Min_costflow()
{
int ans = 0;
int maxflow = 0;
while(spfa())
{
int minx = INF;
for(int i = t; i != s; i = pre[i])
{
minx = min(minx, edge[path[i]].f);
}
maxflow += minx;
ans += dis[t]*minx;
for(int i = t; i != s; i = pre[i])
{
edge[path[i]].f -= minx;
edge[path[i]^1].f += minx;
}
}
return ans;
}
int main()
{
while(~scanf("%d%d", &n, &m))
{
init();
int a, b, c, d;
for(int i = 1; i <= n; i++)
{
scanf("%d%d%d%d", &a, &b, &c, &d);
addEdge(s, i, b, a);
addEdge(i, t, d, -c);
}
for(int i = 1; i <= m; i++)
{
scanf("%d %d %d", &a, &b, &c);
if(a == b) continue;
addEdge(a, b, INF, c);
addEdge(b, a, INF, c);
}
printf("%d\n", -Min_costflow());
}
return 0;
}