k种货物分开求解最小费用最大流,主要减少了寻找最短路的时间。

  

#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxe 256000 //pay
#define maxv 5120 //pay
#define maxn 55 //pay
#define sc scanf
#define pt printf
#define rep(i,a,b) for(int i=(a);i<(b);++i)
const int inf = 0x3f3f3f3f;
int fee,cg,sp,need;
int N,M,K ,s,t;
typedef struct ed{
int v,nxt,cap,dis;
}ed;
ed e[maxe];
int nxt[maxe],tot,head[maxv],vis[maxv],d[maxv],bk[maxv];
int mp[maxn][maxn][maxn];
int mi(int a,int b) {return a<b?a:b;}
void add(int u,int v,int cap,int dis)
{
e[tot].v=v; e[tot].nxt=head[u];
e[tot].dis=dis; e[tot].cap=cap;
head[u]=tot++; e[tot].v=u; e[tot].nxt=head[v];
e[tot].dis=-dis; e[tot].cap=;
head[v]=tot++;
}
int spfa()
{
queue<int> q;
int u = s,v;
q.push(u);
while(!q.empty())
{
u = q.front(); q.pop();
vis[u] = ;
for(int i = head[u];~i;i=e[i].nxt)
{
if(e[i].cap<) continue;
v = e[i].v;
if(d[u]+e[i].dis<d[v])
{
bk[v]=i;
d[v] = d[u]+e[i].dis;
if(vis[v]==)
{
q.push(v);
vis[v]=;
}
}
}
}
return d[t]!=inf;
} void init()
{
tot=;
memset(head,-,sizeof(head)); //pay
}
int cust_need[maxn][maxn];
int halt_prov[maxn][maxn];
//第一次改进:如果仓库这种东西的存量为0或者客户需求为0,他们之间不建立边 —— 居然RE了
int main()
{
freopen("in.txt","r",stdin);
d[]=; bk[]=-;
while()
{
need = fee = sp = ;
sc("%d%d%d",&N,&M,&K); //pt("%d %d %d\n",N,M,K);
if(N==&&M==&&K==) break;
s=,t=+N+M;
int i,j,k;
memset(mp,-,sizeof(mp));
for(i=;i<N;++i) for(j=;j<=K;++j) sc("%d",&cust_need[i][j]),need+=cust_need[i][j];
for(i=;i<M;++i) for(j=;j<=K;++j) sc("%d",&halt_prov[i][j]);
for(k=;k<=K;++k) for(i=;i<N;++i) for(j=;j<M;++j)
{
sc("%d",&mp[k][i][j]);
if(halt_prov[j][k]==||cust_need[i][k]==) continue;
add(j*K+k,K*M+i*K+k,mi(halt_prov[j][k],cust_need[i][k]),mp[k][i][j]);
}
for(k=;k<=K;++k)
{
init();
for(i=;i<N;++i) if(cust_need[i][k]>) add(+M+i,t,cust_need[i][k],);
for(j=;j<M;++j) if(halt_prov[j][k]>) add(,+j,halt_prov[j][k],);
for(i=;i<N;++i) for(j=;j<M;++j)
{
if(halt_prov[j][k]==||cust_need[i][k]==) continue;
add(+j,+M+i,mi(halt_prov[j][k],cust_need[i][k]),mp[k][i][j]);
}
while()
{
for(i=;i<=t;++i) d[i]=inf,vis[i]=;
if(spfa()==) break;
int min_flow = inf;
cg=bk[t];
while(cg!=-)
{
min_flow = mi(min_flow,e[cg].cap);
cg=bk[e[cg^].v];
}
sp+=min_flow;
cg=bk[t];
while(cg!=-)
{
e[cg].cap-=min_flow;
e[cg^].cap+=min_flow;
fee+=e[cg].dis*min_flow;
cg=bk[e[cg^].v];
}
}
}
if(sp==need) pt("%d\n",fee); // write(fee), pt("\n");
else pt("-1\n");
} return ;
}

POJ 2516

最新文章

  1. Entity Framework 6 Recipes 2nd Edition(11-2)译 -&gt; 用”模型定义”函数过滤实体集
  2. ASP.NET Core 中文文档 第三章 原理(14)服务器
  3. [LeetCode] Divide Two Integers 两数相除
  4. .NET 扩展方法 (二)
  5. sun.misc.Unsafe的理解
  6. MyBatis SQL动态装配
  7. KnockoutJS 3.X API 第三章 计算监控属性(3) KO如何实现依赖追踪
  8. Android GPS 临近触发
  9. 后台获取不规则排列RadioButton组的值
  10. Windows 7下安装部署NodeJs
  11. set and Sequence theory
  12. spring security 11种过滤器介绍
  13. 学习整理与细化(1)——Internet 的域名系统(domain name system)
  14. Android5.0新特性之——按钮点击效果动画(涟漪效果)
  15. macOS10.4后的刻盘新姿势
  16. HDU 2459 Maximum repetition substring
  17. 复选框批量删除操作-jquery方式
  18. zabbix使用自定义key进行监控
  19. Python网络爬虫相关基础概念
  20. druid的配置

热门文章

  1. Linux 修改hostname几种方式
  2. Mysql8- Public Key Retrieval is not allowed
  3. ftp服务端
  4. 更新SVN时提示要清理,但清理失败,乱码得解决方案
  5. vue的v-cloak 指令设置样式
  6. vue.js(12)--过滤器
  7. over partition by
  8. springboot通过继承OncePerRequestFilter,在拦截器中@Autowired 为null问题
  9. pycharm安装第三方库失败module &#39;pip&#39; has no attribute &#39;main&#39;
  10. Categorical Data