旧题重WA 233

原题:

 n<=2000

一眼费用流,简单

拆点,s到入点流量∞费用p表示直接买,入点到出点r[i]表示每天必须有r[i]条,出点到t流量∞用来保证边被鸽掉,出点再到i+m或i+n的入点表示洗了,入点到下一天的入点流量∞表示洗过的可以屯着

然后样例就过不了233

翻以前的博客,发现我三年前第一次做这题的时候就犯了同样的错误233

我之前的博客认为错误在于如果选择洗,那么这条餐巾的费用为买+洗,大于直接买,所以不会增广

这个解释不对,费用流就是在保证最大流的情况下费用最小,那么我先买再洗,每条边跑的也是满流,费用更低,为什么费用流得不到方案???

费用更低是肯定的,费用流也没问题,问题就在于每条边跑满流可不等于最大流

这个错误主要还是在最大流最小割的概念上不清楚

把中间的边全鸽了,所用流量确实是最大流

但是上面的建图如果先买再洗,那么一条流鸽了两条边,总流量不是最大流

最大流最小割定理只能证明二者在数值上相等

事实上,如果买+洗方案跑完的残余网络(包括反边)画出来,就可以发现有一条从源到入点,再从入点走反边到出点的流量

这条反边虽然让费用增加,但也给从源到汇提供了再跑一次的机会

所以由此可以总结经验,注意最大流一定是从源点到汇点的流量呀

知道了错误的本质,正解其实不难理解

为了避免之前的错误,我们要保证每条干净毛巾(不管是买的还是洗的)都必须占用一条从源到汇的完整流量

需要注意到一个关键性质,每天会稳定地产生r[i]条脏毛巾

那么我们产销分离,把买的和洗的分开考虑

因为每天固定会产脏毛巾,所以也不需要再从干净的毛巾里引一条边出来表示洗

直接把每天拆称脏点和好点,然后从脏点到i+m或i+n天的好点连边,然后源再到脏点流量为r[i],表示每天最多产r[i]条脏毛巾

源点再到好点连边,表示直接买,好点到汇点流量为r[i],表示每天必须要攒够r[i]条好毛巾

最后,好点到下一天的好点连边表示屯毛巾就行了

代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 #define LL long long
 8 int rd(){int z=0,mk=1;  char ch=getchar();
 9     while(ch<'0'||ch>'9'){if(ch=='-')mk=-1;  ch=getchar();}
10     while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}
11     return z*mk;
12 }
13 const int oo=1000000007;
14 struct edg{int nxt,y,v,u;}e[31000];  int lk[4100],ltp=1;
15 void ist(int x,int y,int z,int w){
16     e[++ltp]=(edg){lk[x],y,z,w};  lk[x]=ltp;
17     e[++ltp]=(edg){lk[y],x,0,-w};  lk[y]=ltp;
18 }
19 int n,m,ft,st,fc,sc,a[2100];
20 int s,t;
21 int dstc[4100];
22 int q[41000],hd=0;  bool vstd[4100];
23 int lst[4100],lse[4100];
24 bool spfa(){
25     for(int i=1;i<=t;++i){
26         vstd[i]=false;
27         dstc[i]=oo;
28     }
29     dstc[q[hd=1]=s]=0;
30     for(int k=1;k<=hd;++k){
31         for(int i=lk[q[k]];i;i=e[i].nxt)
32             if(e[i].v && dstc[q[k]]+e[i].u<dstc[e[i].y]){
33                 dstc[e[i].y]=dstc[q[k]]+e[i].u;
34                 lst[e[i].y]=q[k],lse[e[i].y]=i;
35                 if(!vstd[e[i].y]){
36                     q[++hd]=e[i].y;
37                     vstd[e[i].y]=true;
38                 }
39             }
40         vstd[q[k]]=false;
41     }
42     //return dstc[t];  注意不是判断dstc[t]不为0
43     return dstc[t]!=oo;
44 }
45 LL cstflw(){
46     LL bwl=0;
47     while(spfa()){
48         int flw=oo;
49         for(int i=t;i!=s;i=lst[i])
50             flw=min(flw,e[lse[i]].v);
51         for(int i=t;i!=s;i=lst[i]){
52             bwl+=flw*e[lse[i]].u;
53             e[lse[i]].v-=flw,e[lse[i]^1].v+=flw;
54             //cout<<i<<"<-";
55         }
56         //cout<<endl;
57     }
58     return bwl;
59 }
60 int main(){
61     //freopen("ddd.in","r",stdin);
62     cin>>n;
63     for(int i=1;i<=n;++i)  a[i]=rd();
64     cin>>m>>ft>>fc>>st>>sc;
65     s=n+n+1,t=n+n+2;
66     for(int i=1;i<=n;++i){
67         /*ist(i,i+n,a[i],0);
68         ist(s,i,oo,m);
69         ist(i+n,t,oo,0);
70         if(i<n)  ist(i,i+1,oo,0);
71         if(i+ft<=n)  ist(i+n,i+ft,oo,fc);
72         if(i+st<=n)  ist(i+n,i+st,oo,sc);*/
73         ist(s,i+n,oo,m);
74         ist(i+n,t,a[i],0);
75         ist(s,i,a[i],0);
76         if(i<n)  ist(i,i+1,oo,0);
77         if(i+ft<=n)  ist(i,i+ft+n,oo,fc);
78         if(i+st<=n)  ist(i,i+st+n,oo,sc);
79     }
80     cout<<cstflw()<<endl;
81     return 0;
82 }
View Code
01-04 12:26