[单纯形]bzoj1061 - cool's Blog
[单纯形]bzoj1061
1061: [Noi2008]志愿者招募
Time Limit: 20 Sec Memory Limit: 162 MBSubmit: 3017 Solved: 1866
[Submit][Status][Discuss]
Description
申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。
Input
第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负整数，表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。
Output
仅包含一个整数，表示你所设计的最优方案的总费用。
Sample Input
2 3 4
1 2 2
2 3 5
3 3 2
Sample Output
HINT
招募第一类志愿者3名，第三类志愿者4名 30%的数据中，1 ≤ N, M ≤ 10，1 ≤ Ai ≤ 10； 100%的数据中，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均 不超过2^31-1。
这道题标算是费用流（话说有哪道题标算是单纯形的！）
不过当胡主力讲了单纯形可以艹大多数网络流的题目的时候，我感觉我这个不会网络流的蒟蒻有了希望
单纯形真的挺难理解的，幸亏zhzx的毛主力最后提点了一把！
单纯形就是解这样一个问题
Σa[i][j]*xj<=b[i]
最大化Σc[i]*xi
当要最小化一个式子的时候，就要用到对偶式的概念（具体我也不是很清楚）
然后就可以直接贴板子了
namespace DCX{
double A[101][20010],b[20010],c[110],v;
void Pivot(int l,int e)
{
int i,j;
b[l]/=A[l][e];
for(i=1;i<=n;i++)if(i!=e) A[l][i]/=A[l][e];
A[l][e]=1/A[l][e];
for(i=1;i<=m;i++)
if(i!=l&&fabs(A[i][e])>EPS)
{
b[i]-=A[i][e]*b[l];
for(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];
}
v+=c[e]*b[l];
for(i=1;i<=n;i++)
if(i!=e)c[i]-=c[e]*A[l][i];
c[e]=-c[e]*A[l][e];
}
double Simplex()
{
int i,l,e;
while(1)
{
for(i=1;i<=n;i++)
if(c[i]>EPS)break;
if((e=i)==n+1)return v;
double temp=INF;
for(i=1;i<=m;i++)
if(A[i][e]>EPS && b[i]/A[i][e]<temp)
temp=b[i]/A[i][e],l=i;
if(temp==INF) return INF;
Pivot(l,e);
}
}
}
/*
m表示共有 元 X1……Xm
n表示共有n个限制
a[i][j]表示第i个限制中Xj的系数
b[i]表示第i个限制的常数
c[i]表示在目标式中Xi的系数
限制都是<=
此时是最大化目标式
最小化互换即可
*/
单纯形唯一的缺点就是比较费空间，不过貌似可以用类似边表的存，不过太弱（lan）了没准备写。
zjoi2013防守战线也是道（费用流）单纯形好题
评论 (0)