【Training Contest】2016.03.08

【Training Contest】2016.04.20 HNOI2016 DAY1

【学习】单纯形法

Jacinth posted @ 2016年3月20日 15:12 in ZHOJ with tags BZOJ Learning 单纯形法费用流学习 , 677 阅读

%%%hzw

表示没学过线性规划就来学这玩意QAQ。。听说拿来骗分很好用。。时间复杂度玄学？[O_{（跑得过）}

BZOJ-1061 单纯形板子题

[Noi2008]志愿者招募

Description	申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。
Input	第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。接下来的一行中包含N 个非负整数，表示每天至少需要的志愿者人数。接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。
Output	仅包含一个整数，表示你所设计的最优方案的总费用。
Sample Input	3 3 2 3 4 1 2 2 2 3 5 3 3 2
Sample Output	14
Hint	招募第一类志愿者3名，第三类志愿者4名 30%的数据中，1 ≤ N, M ≤ 10，1 ≤ Ai ≤ 10； 100%的数据中，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均不超过2^31-1。

听说是单纯形裸题。。费用流建图好题。。

两个方法都试了一遍。。。（谁说单纯形跑得慢？难道窝费用流写炸？

Problem	Result	Memory	Time	Code_Length
1061	Accepted	80344 kb	1172 ms	1376 B
1061	Accepted	3264 kb	1424 ms	1804 B

还是把两个代码都贴在这里吧

BZOJ-1061-单纯形法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63	`//单纯形板子题` `#include <cmath>` `#include <cstdio>` `#include <cstring>` `#include <iostream>` `#include <algorithm>` `#define INF 1e10` `#define eps 1e-7` `#define NN 1010` `#define MM 10010` `using` `namespace` `std;` `int` `n,m;` `double` `a[MM][NN],b[MM],c[NN],v,ans;` `struct` `S` `{` `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` `tmp=INF;` `for` `(i=1;i<=m;++i)` `if` `(a[i][e]>eps && b[i]/a[i][e]<tmp) tmp=b[i]/a[i][e], l=i;` `if` `(tmp==INF)` `return` `INF;` `Pivot(l,e);` `}` `}` `}Simplex;` `int` `main()` `{` `scanf("%d%d",&n,&m);` `for` `(int` `i=1;i<=n;++i)` `scanf("%lf",&c[i]);` `for` `(int` `i=1;i<=m;++i)` `{` `int` `x,y,z;` `scanf("%d%d%d",&x,&y,&z);` `for` `(int` `j=x;j<=y;++j) a[i][j]=1; b[i]=z;` `}` `ans=Simplex.simplex();` `printf("%d\n",int(ans+0.5));` `return` `0;` `}`

BZOJ-1061-费用流法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67	`//费用流` `#include <iostream>` `#include <cstdio>` `#include <cmath>` `#include <cstring>` `#include <cstdlib>` `#include <algorithm>` `#include <queue>` `#define LL long long` `#define NN 2010` `#define MM 100010` `#define INF 0x3f3f3f3f` `using` `namespace` `std;` `int` `n,m,x,y,z,dis[NN],head[NN],fa[NN],need[NN],S,T,tot=1;` `bool` `vis[NN];` `LL ans=0;` `struct` `REC` `{` `int` `v,ne,w,c,u;` `}e[MM];` `queue<int>que;` `void` `Build(int` `xx,int` `yy,int` `zz,int` `cc)` `{` `e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz, e[tot].c=cc, e[tot].u=xx;` `e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx, e[tot].w=0, e[tot].c=-cc, e[tot].u=yy;` `}` `bool` `SPFA()` `{` `while` `(!que.empty()) que.pop();` `memset(dis,INF,sizeof(dis));` `memset(vis,0,sizeof(vis));` `dis[S]=0, que.push(S), vis[S]=1;` `while` `(!que.empty())` `{` `int` `now=que.front(); que.pop();` `for` `(int` `i=head[now];i;i=e[i].ne)` `if` `(e[i].w && dis[e[i].v]>dis[now]+e[i].c)` `{` `dis[e[i].v]=dis[now]+e[i].c; fa[e[i].v]=i;` `if` `(!vis[e[i].v]) vis[e[i].v]=1, que.push(e[i].v);` `}` `vis[now]=0;` `}` `return` `dis[T]!=INF;` `}` `void` `MCF()` `{` `int` `xx=INF;` `for` `(int` `i=fa[T];i;i=fa[e[i].u]) xx=min(xx,e[i].w);` `for` `(int` `i=fa[T];i;i=fa[e[i].u]) ans+=(LL)xx*e[i].c, e[i].w-=xx, e[i^1].w+=xx;` `}` `int` `main()` `{` `scanf("%d%d",&n,&m); S=n+2, T=n+3;` `for` `(int` `i=1;i<=n;++i)` `scanf("%d",&need[i]);` `for` `(int` `i=1;i<=m;++i)` `scanf("%d%d%d",&x,&y,&z), Build(x,y+1,INF,z);` `need[0]=need[n+1]=0;` `int` `tmp;` `for` `(int` `i=1;i<=n+1;++i)` `if` `((tmp=need[i]-need[i-1])>=0) Build(S,i,tmp,0);` `else` `Build(i,T,-tmp,0);` `for` `(int` `i=1;i<=n;++i) Build(i+1,i,INF,0);` `while` `(SPFA()) MCF();` `printf("%lld\n",ans);` `return` `0;` `}`

评论 (0)