国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

BZOJ 1061, 志愿者招募

2019-11-11 05:44:18
字體:
來源:轉載
供稿:網友

PRoblem

傳送門

Mean

最小化招聘給定不同類型志愿者,以滿足每日不同人數要求的費用總和。

Analysis

由線性規劃轉化為最小費用最大流來處理。 一般按如下步驟進行操作: ①添加松弛變量,將不等號都變為等號。分別用下一個式子減去上一個式子,如果每個變量只出現了兩次且符號一正一負,那么可以轉化為費用流。 ②對于每個式子建立一個點,那么每個變量對應一條邊,從一個點流出,向另一個點流入。 ③對于等式右邊的常數C,如果是的,對應從源點向該點連一條流量C,費用0的邊;如果是的對應從該點向匯點連一條流量?C,費用0的邊。 ④對于每個變量,從它系數為正的式子向系數為負的式子連一條容量為INF,費用為它在目標函數里系數的邊。 這樣網絡流模型就構造完畢了。

Code

#include<cstdio>const int N=1005,M=45005,INF=~0U>>2;int n,m,s,t,l,r,x,y,z,ed=1,i,tmp,ans,a[N],g[N],nxt[M],u[M],v[M],c[M],co[M],q[M],d[N],f[N];bool in[N];void add(int x,int y,int z,int zo){ u[++ed]=x,v[ed]=y,c[ed]=z,co[ed]=zo,nxt[ed]=g[x],g[x]=ed; u[++ed]=y,v[ed]=x,c[ed]=0,co[ed]=-zo,nxt[ed]=g[y],g[y]=ed;}bool SPFA(){ for(int i=1;i<=t;i++) d[i]=INF,in[i]=0; in[s]=1,q[l=r=M>>1]=s; while(l<=r){ int x=q[l++]; if(x==t) continue; for(int i=g[x];i;i=nxt[i]) if(c[i] && d[v[i]]>d[x]+co[i]){ d[v[i]]=d[x]+co[i]; f[v[i]]=i; if(!in[v[i]]){ if(d[v[i]]<d[q[l]]) q[--l]=v[i]; else q[++r]=v[i]; in[v[i]]=1; } } in[x]=0; } return d[t]<INF;}int main(){ scanf("%d%d",&n,&m); t=n+2; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n+1;i++){ tmp=a[i]-a[i-1]; if(tmp>0) add(s,i,tmp,0); else add(i,t,-tmp,0); } for(i=n+1;i>1;i--) add(i,i-1,INF,0); for(i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); add(x,y+1,INF,z); } while(SPFA()){ for(tmp=INF,i=t;i!=s;i=u[f[i]]) if(tmp>c[f[i]]) tmp=c[f[i]]; for(ans+=d[i=t]*tmp;i!=s;i=u[f[i]]) c[f[i]]-=tmp,c[f[i]^1]+=tmp; } printf("%d",ans); return 0;}
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 蓬莱市| 泰兴市| 商丘市| 澄迈县| 孟连| 兰溪市| 乐平市| 顺昌县| 蓝田县| 东海县| 历史| 望谟县| 鸡泽县| 上栗县| 济南市| 中方县| 丰顺县| 应城市| 炉霍县| 洞口县| 澄城县| 云南省| 张家港市| 台东市| 全州县| 南华县| 汤原县| 阿合奇县| 绥德县| 鄂托克前旗| 西盟| 永年县| 新疆| 离岛区| 松阳县| 肃宁县| 剑阁县| 调兵山市| 山丹县| 丽水市| 云霄县|