宝安卫生信息网温馨提示：加载中，请稍候...1550人阅读
网络流（22）
最小费用流问题。。。。。盗用了小群的模版。。。哇咔咔。。。。之前一直是保存前驱点和前驱边来求解。。。。想不到小群很诡异的只保存反向边就可以了。。。。。。。。。。。。很厉害。。。
【问题分析】
网络优化问题，用最小费用最大流解决。
【建模方法】
把每天分为二分图两个集合中的顶点Xi,Yi，建立附加源S汇T。
1、从S向每个Xi连一条容量为ri，费用为0的有向边。
2、从每个Yi向T连一条容量为ri，费用为0的有向边。
3、从S向每个Yi连一条容量为无穷大，费用为p的有向边。
4、从每个Xi向Xi+1(i+1&=N)连一条容量为无穷大，费用为0的有向边。
5、从每个Xi向Yi+m(i+m&=N)连一条容量为无穷大，费用为f的有向边。
6、从每个Xi向Yi+n(i+n&=N)连一条容量为无穷大，费用为s的有向边。
求网络最小费用最大流，费用流值就是要求的最小总花费。
【建模分析】
这个问题的主要约束条件是每天的餐巾够用，而餐巾的来源可能是最新购买，也可能是前几天送洗，今天刚刚洗好的餐巾。每天用完的餐巾可以选择送到快洗部或慢洗部，或者留到下一天再处理。
经过分析可以把每天要用的和用完的分离开处理，建模后就是二分图。二分图X集合中顶点Xi表示第i天用完的餐巾，其数量为ri，所以从S向Xi连接容量为ri的边作为限制。Y集合中每个点Yi则是第i天需要的餐巾，数量为ri，与T连接的边容量作为限制。每天用完的餐巾可以选择留到下一天（Xi-&Xi+1），不需要花费，送到快洗部(Xi-&Yi+m)，费用为f，送到慢洗部(Xi-&Yi+n)，费用为s。每天需要的餐巾除了刚刚洗好的餐巾，还可能是新购买的(S-&Yi)，费用为p。
在网络上求出的最小费用最大流，满足了问题的约束条件（因为在这个图上最大流一定可以使与T连接的边全部满流，其他边只要有可行流就满足条件），而且还可以保证总费用最小，就是我们的优化目标。
#include&iostream&
#include&cstdio&
#include&cstring&
#define inf
#define M 2010
#define N 20000
#define cc(m,v) memset(m,v,sizeof(m))
struct node{
int v,f,c,
int head[M],p,pre[M],dis[M],vis[M];
int que[N];
void ainit(){
p=0,cc(head,-1);
void addedge(int u,int v,int f,int c){
edge[p].v=v,edge[p].f=f,edge[p].c=c,edge[p].next=head[u],head[u]=p++;
edge[p].v=u,edge[p].f=0,edge[p].c=-c,edge[p].next=head[v],head[v]=p++;
bool spfa(int s,int t,int n){
int i,u,v,qin=0,qout=0;
for(i=0;i&=n;i++) dis[i]=inf,vis[i]=0;
dis[s]=0,pre[s]=pre[t]=-1,que[qin++]=s;
while(qout!=qin){
u=que[qout++],vis[u]=0;
if(qout==N) qout=0;
for(i=head[u];i!=-1;i=edge[i].next)
if(edge[i].f && (edge[i].c+dis[u]&dis[v=edge[i].v])){
dis[v]=dis[u]+edge[i].c,pre[v]=i^1;
if(!vis[v]){
vis[v]=1,que[qin++]=v;
if(qin==N) qin=0;
return pre[t]&=0;
int spfaflow(int s,int t,int n){
int i,f,ans=0;
while(spfa(s,t,n)){
for(i=pre[t],f=i&=0;i=pre[edge[i].v])
if(edge[i^1].f&f) f=edge[i^1].f;
for(i=pre[t];i&=0;i=pre[edge[i].v])
edge[i].f+=f,edge[i^1].f-=f;
ans+=f*dis[t];
int main(){
int na,pa,ma,fa,naa,sa,i,u;
while(scanf(&%d%d%d%d%d%d&,&na,&pa,&ma,&fa,&naa,&sa)!=-1){
int s=0,t=na*2+1;
for(i=1;i&=i++){
scanf(&%d&,&u);
addedge(s,i,u,0),addedge(i+na,t,u,0);
addedge(s,i+na,inf,pa);
if(i&na) addedge(i,i+1,inf,0);
if(i+ma&=na) addedge(i,i+ma+na,inf,fa);
if(i+naa&=na) addedge(i,i+naa+na,inf,sa);
printf(&%d\n&,spfaflow(s,t,t+1));
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：60028次
积分：1288
积分：1288
排名：千里之外
原创：71篇
(21)(43)(9)“世界艾滋病日”宣传活动今天在南昌举行
《国家卫生计生委关于修改<外...
《国家卫生计生委决定废止<农...
嘉宾：南昌大学附属口腔医院主任医师曾利伟、陈林林、欧晓艳、叶芳，副主任医师黄美贞、史彦
省妇幼保健院副主任医师
江西卫生报记者
时间：1月8日
嘉宾：梁 斌 省卫计委医政医管处副处长
张小康 江西省儿童医院院长
伟 昌大一附医院副院长
张志平 九江附属医院
时间：admin
嘉宾：程晓曙 南大二附院院长
罗礼生 省卫计委医政医管处处长
徐建军 南大二附院院长助理
郑健林 修水县人民医院院长
时间：admin
嘉宾：曾传美 江西省卫计委副主任
吕农华 南大一附院副院长
车达平 南昌市卫计委副主任
邹卫兵 新余市人民医院院长
苏 健 鹰潭市人民医院院长
陈 军 横峰县人民医院院长
时间：admin
嘉宾：程晓曙 南大二附院院长
罗礼生 省卫计委医政医管处处长
徐建军 南大二附院院长助理
郑健林 修水县人民医院院长
时间：admin
嘉宾：叶 颖 江西省卫生计生委妇幼健康服务处副处长
张辉丽 江西省卫生计生委妇幼健康服务处主任科员
张倩平 江西省妇幼保健院妇女保健科科长
廖珠根 江西省妇幼保健院儿童保健科科长
时间：admin
嘉宾：罗礼生 省卫生计生委医政医管处处长
马强 省儿童医院副院长
王卓 省卫生计生委医政医管处主任科员
时间：admin
嘉宾：刘希伟 江西省中医管理副局长
吴磊军 九江市卫生局副局长
邵尤青 都昌县中医院院长
时间：admin
嘉宾：江西省卫生厅医政处处长罗礼生，江西省精神病院副院长、主任医师魏波，江西省精神病院公共卫生科科长余雪虎
时间：admin
嘉宾：江西省疾病预防控制中心主任医师、江西省人感染H7N9禽流感防控专家组成员谢昀
时间：admin
嘉宾：江西省卫生厅法监局副局长叶颖、江西省卫生监督所监督二科科长、江西省饮用水卫生监督首席监督员李建平、南昌市卫生监督所监督副所长、江西省饮用水卫生监督首席监督员刘波、江西省疾病预防控制中心环境所副所长、主任医师何加芬
时间：admin
嘉宾：江西省卫生厅医政处副处长梁斌、江西省卫生厅医政处张鹰、江西省人民医院肾内科主任、主任医师李?
时间：admin
嘉宾：省卫生厅药政处处长贾立明、省妇幼保健院周小飞、南昌大学第一附属医院舒徐、南昌县向塘中心医院蔡阿军
时间：admin
嘉宾：省卫生厅副厅长曾传美，厅监察室、疾控处、医政处、医管处、法监处等有关负责人
时间：admin
嘉宾：省卫生厅、省发改委、省财政厅、省审计厅、省人社厅、省工商局、省食药监局有关负责人
--设区市卫生计生部门--
南昌市卫生和计划生育委员会
九江市卫生和计划生育委员会
景德镇市卫生和计划生育委员会
萍乡市卫生和计划生育委员会
鹰潭市卫生和计划生育委员会
赣州市卫生和计划生育委员会
宜春市卫生和计划生育委员会
上饶市卫生和计划生育委员会
抚州市人口和计划生育委员会
---省直卫生计生单位---
省人民医院
南昌大学第一附属医院
南昌大学第二附属医院
南昌大学附属口腔医院
南昌大学第四附属医院
江西中医药大学附属医院
赣南医学院第一附属医院
井冈山大学附属医院
江西省肿瘤医院
江西省妇幼保健院
江西省儿童医院
江西省惠民医院（省直属门诊部）
江西省庐山疗养院
省医学科学研究院
江西省疾病预防控制中心
省寄生虫病防治研究所
江西省职业病防治研究院
江西省卫生监督所
江西省中医药研究院
江西省血液中心
江西省医药采购服务中心
省卫生计生委信息中心
南昌大学附属眼科医院
全国各省级卫生计生部门
重庆市卫生和计划生育委员会
浙江省卫生和计划生育委员会
云南省卫生和计划生育委员会
新疆生产建设兵团卫生局
新疆生产建设兵团人口与计划生育委员会
天津市卫生和计划生育委员会
四川省卫生和计划生育委员会
上海市卫生和计划生育委员会
陕西省卫生和计划生育委员会
山西省卫生和计划生育委员会
山东省卫生和计划生育委员会
青海省卫生和计划生育委员会
宁夏回族自治区卫生和计划生育委员会
辽宁省卫生和计划生育委员会
江苏省卫生和计划生育委员会
吉林省卫生和计划生育委员会
湖南省卫生和计划生育委员会
湖北省卫生和计划生育委员会
黑龙江省卫生和计划生育委员会
河南省卫生和计划生育委员会
河北省卫生和计划生育委员会
海南省卫生和计划生育委员会
贵州省卫生和计划生育委员会
广西壮族自治区卫生计生委
广东省卫生和计划生育委员会
甘肃省卫生和计划生育委员会
福建省卫生和计划生育委员会
大连市卫生和计划生育委员会
北京市卫生和计划生育委员会
安徽省卫生和计划生育委员会
-----省政府各部门-----
发展和改革委员会
人力资源和社会保障厅
交通运输厅
住房和城乡建设厅
工业和信息化委员会
环境保护厅
民族宗教事务局
质量技术监督局
省新闻出版广电局
外事侨务办
国土资源厅
食品药品监管局
通信管理局
工业经济联合会
出入境检验检疫局
煤矿安全监察局
减灾委员会
安全生产监管局
扶贫和移民办公室
国防科工办
江西政法网
人行南昌中心支行
省国家保密局
省邮政管理局
-------友好链接-------
中国政府门户网站
中华人民共和国国家卫生和计划生育委员会
国家中医药管理局
中国文明网
中国江西网
江西省人民政府
江西文明网
江西卫生人才人事网
江西远程医学教育网
