首页 > 代码库 > BZOJ1061 NOI2008 志愿者招募 单纯形
BZOJ1061 NOI2008 志愿者招募 单纯形
题意：给定M个志愿者和工作时间的长度N，每个志愿者由工作时间[l,r]和费用c来描述，每个单位时间需要t名志愿者，保证有解，求最少总花费。
题解：
（公式太多就用图片代替了QAQ）
这个题标算貌似是费用流啊，不太清楚……总而言之设x[i]为i这个人要不要，b[i]为各个时间所需的志愿者数量，a[i][j]为i时间j这名志愿者能不能起作用，c[i]为i的费用，然后就是裸的线性规划
#include <cmath>#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define INF 1e10#define eps 1e-6const int MAXN=1000+2;const int MAXM=10000+2;int N,M;double a[MAXM][MAXN],b[MAXM],c[MAXN];double Pivot(int l,int e){ b[l]/=a[l][e]; for(int i=1;i<=N;i++) if(i!=e) a[l][i]/=a[l][e]; a[l][e]=1/a[l][e]; for(int i=1;i<=M;i++) if(i!=l && fabs(a[i][e])>eps){ b[i]-=a[i][e]*b[l]; for(int j=1;j<=N;j++) if(j!=e) a[i][j]-=a[i][e]*a[l][j]; a[i][e]=-a[i][e]*a[l][e]; } double ret=c[e]*b[l]; for(int i=1;i<=N;i++) if(i!=e) c[i]-=c[e]*a[l][i]; c[e]=-c[e]*a[l][e]; return ret;}double Simplex(){ int e,l; double ret=0; while(1){ e=-1; for(int i=1;i<=N;i++) if(c[i]>0){ e=i; break; } if(e==-1) return ret; double t=INF; for(int i=1;i<=M;i++) if(a[i][e]>eps && b[i]/a[i][e]<t) t=b[i]/a[i][e],l=i; if(t==INF) return INF; ret+=Pivot(l,e); }}int main(){ cin >> N >> M; for(int i=1;i<=N;i++) scanf("%lf",c+i); for(int i=1,x,y,z;i<=M;i++){ scanf("%d %d %d",&x,&y,&z); for(int j=x;j<=y;j++) a[i][j]=1; b[i]=z; } cout << (int)(Simplex()+0.5) << endl; return 0;}
BZOJ1061 NOI2008 志愿者招募 单纯形
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。