「BZOJ1391」[Ceoi2008] order
Description
有N个工作，M种机器，每种机器你可以租或者买过来. 每个工作包括若干道工序，每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。 现在给出这些参数，求最大利润
Input
第一行给出 N,M(1<=N<=1200,1<=M<=1200) 下面将有N块数据，每块数据第一行给出完成这个任务能赚到的钱(其在[1,5000])及有多少道工序 接下来若干行每行两个数，分别描述完成工序所需要的机器编号及租用它的费用(其在[1,20000]) 最后M行，每行给出购买机器的费用(其在[1,20000])
Output
最大利润
Sample Input
2 3
100 2
1 30
2 20
100 2
1 40
3 80
50
80
110
100 2
1 30
2 20
100 2
1 40
3 80
50
80
110
Sample Output
50
HINT
题解
此题dinic要加当前弧优化
不然TAT
cur表示当前弧
|
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 |
#include<iostream> #include<cstring> #include<cstdio> #define inf 0x7fffffff using namespace std; int T,n,m,cnt=1,ans,cur[2501],q[2505],head[2505],h[2505]; struct data{int to,next,v;}e[3000001]; void ins(int u,int v,int w) {cnt++;e[cnt].to=v;e[cnt].v=w;e[cnt].next=head[u];head[u]=cnt;} void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,0);} bool bfs() { int t=0,w=1,i,now; for(int i=1;i<=T;i++)h[i]=-1; q[0]=h[0]=0; while(t!=w) { now=q[t];t++;if(t==2501)t=0; for(i=head[now];i;i=e[i].next) { if(e[i].v&&h[e[i].to]<0) {h[e[i].to]=h[now]+1;q[w++]=e[i].to;if(w==2501)w=0;} } } if(h[T]==-1)return 0;return 1; } int dfs(int x,int f) { if(x==T)return f; int w,used=0; for(int i=cur[x];i;i=e[i].next) { if(e[i].v&&h[e[i].to]==h[x]+1) { w=f-used; w=dfs(e[i].to,min(w,e[i].v)); e[i].v-=w;if(e[i].v>0)cur[x]=i;e[i^1].v+=w; used+=w;if(used==f)return f; } } if(!used)h[x]=-1; return used; } void dinic(){while(bfs()){for(int i=0;i<=T;i++)cur[i]=head[i];ans-=dfs(0,inf);}} int main() { scanf("%d%d",&n,&m); T=n+m+1; int a,b,c,d; for(int i=1;i<=n;i++) { scanf("%d%d",&a,&b); insert(0,i,a);ans+=a; for(int j=1;j<=b;j++) { scanf("%d%d",&c,&d); insert(i,n+c,d); } } for(int i=1;i<=m;i++) { scanf("%d",&a); insert(n+i,T,a); } dinic(); printf("%d",ans); return 0; } |
计数器 9863325
OI 课件=>
OI 课件=>
if(!used)h
=-1; 神犇求这个优化的名字=_=
啊。。这个我一开始学就是这么写的。。
SAP+GAP+当前弧比你的 dinic+当前弧 快 23333
……