「BZOJ2245」[SDOI2011] 工作安排
Description
你的公司接到了一批订单。订单要求你的公司提供n类产品，产品被编号为1~n，其中第i类产品共需要Ci件。公司共有m名员工，员工被编号为1~m员工能够制造的产品种类有所区别。一件产品必须完整地由一名员工制造，不可以由某名员工制造一部分配件后，再转交给另外一名员工继续进行制造。
我们用一个由0和1组成的m*n的矩阵A来描述每名员工能够制造哪些产品。矩阵的行和列分别被编号为1~m和1~n，Ai,j为1表示员工i能够制造产品j，为0表示员工i不能制造产品j。
如果公司分配了过多工作给一名员工，这名员工会变得不高兴。我们用愤怒值来描述某名员工的心情状态。愤怒值越高，表示这名员工心情越不爽，愤怒值越低，表示这名员工心情越愉快。员工的愤怒值与他被安排制造的产品数量存在某函数关系，鉴于员工们的承受能力不同，不同员工之间的函数关系也是有所区别的。
对于员工i，他的愤怒值与产品数量之间的函数是一个Si+1段的分段函数。当他制造第1~Ti,1件产品时，每件产品会使他的愤怒值增加Wi,1，当他制造第Ti,1+1~Ti,2件产品时，每件产品会使他的愤怒值增加Wi,2……为描述方便，设Ti,0=0,Ti,si+1=+∞，那么当他制造第Ti,j-1+1~Ti,j件产品时，每件产品会使他的愤怒值增加Wi,j，1≤j≤Si+1。
你的任务是制定出一个产品的分配方案，使得订单条件被满足，并且所有员工的愤怒值之和最小。由于我们并不想使用Special Judge，也为了使选手有更多的时间研究其他两道题目，你只需要输出最小的愤怒值之和就可以了。
Input
第一行包含两个正整数m和n，分别表示员工数量和产品的种类数；
第二行包含n 个正整数，第i个正整数为Ci；
以下m行每行n 个整数描述矩阵A；
下面m个部分，第i部分描述员工i的愤怒值与产品数量的函数关系。每一部分由三行组成：第一行为一个非负整数Si，第二行包含Si个正整数，其中第j个正整数为Ti,j，如果Si=0那么输入将不会留空行（即这一部分只由两行组成）。第三行包含Si+1个正整数，其中第j个正整数为Wi,j。
Output
仅输出一个整数，表示最小的愤怒值之和。
Sample Input
2 32 2 21 1 0
0 0 1
1
2
1 10
1
2
1 6
Sample Output
HINT
.jpg)
题解
裸费用流
源向每个工作连流量c[i]的边，费用0
每个人向汇点连s[i]+1条边
流量t[i][j]-t[i][j-1],费用w[i][j]
然后工作和人根据A矩阵互相连边
然后直接最小费用最大流
|
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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<cstdio> #include<iostream> #include<cstring> #define T 1001 #define inf 0x7fffffff #define ll long long using namespace std; int n,m,cnt=1;ll ans; int c[251],a[251][251],s[251],t[251][11],w[251][11]; int head[1005],d[1005],q[1005],from[1005]; bool inq[1005]; struct edge{int from,to,next,c,v;}e[500001]; void ins(int u,int v,int w,int c) { cnt++; e[cnt].from=u;e[cnt].to=v; e[cnt].next=head[u];head[u]=cnt; e[cnt].c=c;e[cnt].v=w; } void insert(int u,int v,int w,int c) {ins(u,v,w,c);ins(v,u,0,-c);} bool spfa() { for(int i=0;i<=T;i++)d[i]=inf; int t=0,w=1; d[0]=0;inq[0]=1;q[0]=0; while(t!=w) { int now=q[t];t++;if(t==T)t=0; for(int i=head[now];i;i=e[i].next) if(e[i].v&&d[e[i].to]>d[now]+e[i].c) { d[e[i].to]=d[now]+e[i].c; from[e[i].to]=i; if(!inq[e[i].to]) {inq[e[i].to]=1;q[w++]=e[i].to;if(w==T)w=0;} } inq[now]=0; } if(d[T]==inf)return 0; return 1; } void mcf() { int x=inf; for(int i=from[T];i;i=from[e[i].from]) x=min(x,e[i].v); for(int i=from[T];i;i=from[e[i].from]) { e[i].v-=x; e[i^1].v+=x; ans+=e[i].c*x; } } void build() { for(int i=1;i<=n;i++) insert(0,i,c[i],0); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(a[i][j])insert(j,n+i,inf,0); for(int i=1;i<=m;i++) for(int j=1;j<=s[i]+1;j++) insert(n+i,T,t[i][j]-t[i][j-1],w[i][j]); } int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); for(int i=1;i<=m;i++) { scanf("%d",&s[i]); for(int j=1;j<=s[i];j++) scanf("%d",&t[i][j]); t[i][s[i]+1]=inf; for(int j=1;j<=s[i]+1;j++) scanf("%d",&w[i][j]); } build(); while(spfa())mcf(); printf("%lld",ans); return 0; } |
写了下zkw费用流，然后出奇的慢。。？？是我写错了么
还是什么情况下zkw不适合。。？
|
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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
#include<cstdio> #include<iostream> #include<cstring> #define T 1001 #define inf 0x7fffffff #define ll long long using namespace std; int n,m,cnt=1;ll ans; int c[251],a[251][251],s[251],t[251][11],w[251][11]; int head[1005],d[1005],q[1005]; bool mark[1005]; struct edge{int from,to,next,c,v;}e[500001]; void ins(int u,int v,int w,int c) { cnt++; e[cnt].from=u;e[cnt].to=v; e[cnt].next=head[u];head[u]=cnt; e[cnt].c=c;e[cnt].v=w; } void insert(int u,int v,int w,int c) {ins(u,v,w,c);ins(v,u,0,-c);} bool spfa() { memset(mark,0,sizeof(mark)); for(int i=0;i<=T;i++)d[i]=inf; int t=0,w=1; d[T]=0;mark[T]=1;q[0]=T; while(t!=w) { int now=q[t];t++;if(t==T)t=0; for(int i=head[now];i;i=e[i].next) if(e[i^1].v&&d[e[i].to]>d[now]-e[i].c) { d[e[i].to]=d[now]-e[i].c; if(!mark[e[i].to]) {mark[e[i].to]=1;q[w++]=e[i].to;if(w==T)w=0;} } mark[now]=0; } if(d[0]==inf)return 0; return 1; } int dfs(int x,int f) { if(x==T){mark[T]=1;return f;} int used=0,w; mark[x]=1; for(int i=head[x];i;i=e[i].next) if(!mark[e[i].to]&&e[i].v&&d[x]-e[i].c==d[e[i].to]) { w=f-used; w=dfs(e[i].to,min(e[i].v,w)); ans+=w*e[i].c; e[i].v-=w;e[i^1].v+=w; used+=w;if(used==f)return f; } return used; } void zkw() { while(spfa()) { mark[T]=1; while(mark[T]) { memset(mark,0,sizeof(mark)); dfs(0,inf); } } } void build() { for(int i=1;i<=n;i++) insert(0,i,c[i],0); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(a[i][j])insert(j,n+i,inf,0); for(int i=1;i<=m;i++) for(int j=1;j<=s[i]+1;j++) insert(n+i,T,t[i][j]-t[i][j-1],w[i][j]); } int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); for(int i=1;i<=m;i++) { scanf("%d",&s[i]); for(int j=1;j<=s[i];j++) scanf("%d",&t[i][j]); t[i][s[i]+1]=inf; for(int j=1;j<=s[i]+1;j++) scanf("%d",&w[i][j]); } build(); zkw(); printf("%lld",ans); return 0; } |
OI 课件=>
