简述网站开发设计流程,网络公司网站开发案例,seo标题关键词优化,开发平台需要什么技术题干#xff1a;
度度熊参与了喵哈哈村的商业大会#xff0c;但是这次商业大会遇到了一个难题#xff1a; 喵哈哈村以及周围的村庄可以看做是一共由n个片区#xff0c;m条公路组成的地区。 由于生产能力的区别#xff0c;第i个片区能够花费a[i]元生产1个商品#xff0…题干
度度熊参与了喵哈哈村的商业大会但是这次商业大会遇到了一个难题 喵哈哈村以及周围的村庄可以看做是一共由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] 可能存在重边也可能存在自环。 满足: 1n500, 1m1000, 1a[i],b[i],c[i],d[i],k[i]1000, 1u[i],v[i]n
Output
输出最多能赚多少钱。
Sample Input
2 1
5 5 6 1
3 5 7 7
1 2 1
Sample Output
23
题目大意 给一张图求最小费用。不要求最大流只要求在规定流量内求出最小费用
解题报告
从源点向每一地区i连边费用为a[i]流量为b[i]代表地区i每生产一物品花费。
每一地区i向汇点连边费用为-c[i]流量为d[i]代表地区i每卖出一物品所得。
地区间两两连边费用为地区间距离流量为INF代表每运送一物品花费。
注意若直接求则所求为最大流量条件下费用此时利润不一定最大所以当增广时发现费用为正时直接退出增广此时继续增加流量导致费用变大即继续增加导致最终利润减少。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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[500052];
int n,m;
int head[MAX],d[MAX],vis[MAX],tot,p[MAX];
void add(int u,int v,int c,int cost0) {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; iN; i) d[i]inf,vis[i]0;d[s]0;queueintq;q.push(s);while(!q.empty()) {int uq.front();q.pop();vis[u]0;for(int ihead[u]; ~i; ie[i].ne) {int je[i].to;if(e[i].cd[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 ans0;while(bfs(s,t)) {int xt,finf;while(x!s) {f min(f,e[p[x]].c),xe[p[x]^1].to;}flow f;ans1LL*d[t]*f;xt;while(x!s) {e[p[x]].c-f,e[p[x]^1].cf;xe[p[x]^1].to;}}return ans;
}
int main() {while(~scanf(%d%d,n,m)) {int stn1,edst1;Ned;tot1;memset(head,-1,sizeof(head));for(int a,b,c,d,i 1; in; 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; im; i) {scanf(%d%d%d,x,y,z);add(x,y,inf,z);add(y,x,inf,z);}int ans20;int ansMCMF(st,ed,ans2);printf(%d\n,-ans);}return 0 ;
}
总结
注意和最小费用最大流的区别仅在spfa的时候返回值是0还是INF
