网络流强化-POJ2516
2024-09-05 23:40:15
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
最新文章
- Entity Framework 6 Recipes 2nd Edition(11-2)译 ->; 用”模型定义”函数过滤实体集
- ASP.NET Core 中文文档 第三章 原理(14)服务器
- [LeetCode] Divide Two Integers 两数相除
- .NET 扩展方法 (二)
- sun.misc.Unsafe的理解
- MyBatis SQL动态装配
- KnockoutJS 3.X API 第三章 计算监控属性(3) KO如何实现依赖追踪
- Android GPS 临近触发
- 后台获取不规则排列RadioButton组的值
- Windows 7下安装部署NodeJs
- set and Sequence theory
- spring security 11种过滤器介绍
- 学习整理与细化(1)——Internet 的域名系统(domain name system)
- Android5.0新特性之——按钮点击效果动画(涟漪效果)
- macOS10.4后的刻盘新姿势
- HDU 2459 Maximum repetition substring
- 复选框批量删除操作-jquery方式
- zabbix使用自定义key进行监控
- Python网络爬虫相关基础概念
- druid的配置
热门文章
- Linux 修改hostname几种方式
- Mysql8- Public Key Retrieval is not allowed
- ftp服务端
- 更新SVN时提示要清理,但清理失败,乱码得解决方案
- vue的v-cloak 指令设置样式
- vue.js(12)--过滤器
- over partition by
- springboot通过继承OncePerRequestFilter,在拦截器中@Autowired 为null问题
- pycharm安装第三方库失败module &#39;pip&#39; has no attribute &#39;main&#39;
- Categorical Data