网络流|★ POJ 2516 最小费用最大流（分开计算，K次费用流）网络流|网络流

题意：给你m个供货源，n个店，k种商品，每个店对于每种商品的需求量以及每个供货源运送k种商品到相应店的费用，求最小费用。

分析：
1、直接暴力n*k+m*k个点建图加剪枝勉强过。
2、正解，对于每种物品，分开计算最小费用，最后相加即可。

代码1：

//O(Kn^2m) //如果要求最大费用的话只需在加边的时候加-的边输出时输出-ans即可 #pragma comment(linker,"/STACK:102400000,102400000") #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; //记得必要的时候改成无符号 const int maxn=5005; const int maxm=1000005; const int INF=1000000000; struct EdgeNode { int from; int to; int flow; int cost; int next; }edge[maxm]; int head[maxn],cnt; void add(int x,int y,int z,int c) { edge[cnt].from=x; edge[cnt].to=y; edge[cnt].flow=z; edge[cnt].cost=c; edge[cnt].next=head[x]; head[x]=cnt++; edge[cnt].from=y; edge[cnt].to=x; edge[cnt].flow=0; edge[cnt].cost=-c; edge[cnt].next=head[y]; head[y]=cnt++; }void init() { cnt=0; memset(head,-1,sizeof(head)); }int S,T,n,m; int d[maxn],in[maxn],pre[maxn]; queueQ; bool spfa(int S,int T) { int u,v,f,c; while(!Q.empty())Q.pop(); memset(in,0,sizeof(in)); for(int i=0; i<=n; i++)d[i]=INF; d[S]=0; Q.push(S); while(!Q.empty()) { u=Q.front(); Q.pop(); in[u]=0; for(int i=head[u]; i!=-1; i=edge[i].next){ v=edge[i].to; f=edge[i].flow; c=edge[i].cost; if(f&&d[u]+c 代码2：【网络流|★ POJ 2516 最小费用最大流（分开计算，K次费用流）】 //O(Kn^2m) //如果要求最大费用的话只需在加边的时候加-的边输出时输出-ans即可 #pragma comment(linker,"/STACK:102400000,102400000") #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; //记得必要的时候改成无符号 const int maxn=205; const int maxm=1000005; const int INF=1000000000; struct EdgeNode { int from; int to; int flow; int cost; int next; }edge[maxm]; int head[maxn],cnt; void add(int x,int y,int z,int c) { edge[cnt].from=x; edge[cnt].to=y; edge[cnt].flow=z; edge[cnt].cost=c; edge[cnt].next=head[x]; head[x]=cnt++; edge[cnt].from=y; edge[cnt].to=x; edge[cnt].flow=0; edge[cnt].cost=-c; edge[cnt].next=head[y]; head[y]=cnt++; }void init() { cnt=0; memset(head,-1,sizeof(head)); }int S,T,n,m; int d[maxn],in[maxn],pre[maxn]; queueQ; bool spfa(int S,int T) { int u,v,f,c; while(!Q.empty())Q.pop(); memset(in,0,sizeof(in)); for(int i=0; i 推荐阅读 redis实现延迟消息队列 redis实现im 真正的伏羲八卦图八卦是谁发明的 USBCleaner卸载技巧 USBCleaner如何卸载适合小学生的书包品牌小学一年级书包品牌推荐情侣网名简短好听情侣网名简短好听的有哪些 7天居家健康监测可以上班吗 GIS高端论坛，gis交流网站离职多久后社保被停被辞退的员工多久停社保？绑架罪的追诉期法律绑架犯罪追诉标准是什么我现在得了流行性感冒，会不会得啥病?流行性感冒会不会让我死？同花顺数据分析,数据分析与同花顺的作用华为鸿蒙电脑操作系统测试版,华为鸿蒙OS测试经实践确实有效的老化电池恢复方法如何修改代理服务器的IP地址？代理服务器怎么改ip 血统|小米新机泄露，有高端机血统、中端机颜值，都是米粉期待的设计 kol费用什么意思跨境电商kol什么意思，kol与mcn什么意思向日葵怎么插花瓶好看如何插向日葵好看轻乳酪蛋糕的做法脸上有这特征恐是致命征兆山药豆和红薯一起吃吗 parallels|parallels desktop 解决网络初始化失败问题猎杀IP live|live to inspire 一个普通上班族的流水账0723 流转 Guava|Guava RateLimiter与限流算法自媒体形势分析数学大作战 2018.03.18 星期天的下午茶（一）（小说）月流水几亿的火爆游戏养成记