= =感觉这两天做的最有质量的一道题，尽管以前做过但还是想了一会，建图建的很巧妙. 首先我们很容易可以看出这是一个费用流，然后我们先拆点，把每天分成两个点，一个表示干净的餐巾，一个表示脏的餐巾，这里表示为xi和yi. 然后我们考虑对于每个要表示的量怎么在图中表示出来呢？ 首先我们可以想到每天产生的脏餐巾和消耗的干净餐巾数量是相等的，所以我们没有必要在两点之间连边，我们可以用yi来表示产生的干净餐巾，所以三种途径可以表示为 （我用tf表示快洗用的天数，ts表示慢洗用的天数，cf表示快洗花的钱，cs表示慢洗花的钱） 从源点向每个yi连一条费用为p，容量为inf的边 从xi向y(i+tf)连一条容量为inf费用为cf的边 从xi向y(i+ts)连一条容量为inf费用为cs的边 然后我们再来表示每天需要的餐巾，很好表示 从每个yi向汇点引容量为di，费用为0的边 剩下的就很好表示了 还剩下延期处理的餐巾就是每个xi向x(i+1)连容量为inf费用为1的边 所以图就建好啦，直接跑最小费用最大流就好. 这道题在洛谷上也有，而且双倍经验，但是其中一道时限为4s的题卡常！！ 逼我用zkw费用流我偏不用，然后就加了各种黑科技手写队列然后fread读入优化，循环展开（其实没怎么展开23333），register，inline，前置++加速都用了终于被我卡过去啦哈哈哈哈哈哈哈哈哈，卡常道路还需要慢慢学习.
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>using namespace std;typedef long long ll;const int N=10010,inf=0x3f3f3f3f;int a[N],p[N],inq[N],d[N],head[N],q[N],val[N];int n,ts,s,t,cs,c,cf,qlast,qfront,tf,te,sz;struct edge{ int u,v,cap,cost,flow,next;}e[100010];inline void pop(){++qlast;}inline void push(int QQ){q[++qfront]=qq;}inline int F(){ register int aa,bb;register char ch; while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1); while(ch=getchar(),ch<='9'&&ch>='0')aa=(aa<<3)+(aa<<1)+ch-'0';return bb?aa:-aa;}void add(int u,int v,int cap,int cost){ e[++te].cap=cap; e[te].u=u; e[te].v=v; e[te].flow=0; e[te].next=head[u]; head[u]=te; e[te].cost=cost;}void insert(int u,int v,int cap,int cost){add(u,v,cap,cost);add(v,u,0,-cost);}int spfa(int &flow,ll &cost){ qfront=0,qlast=1; memset(d,0x3f,sizeof(d)); a[s]=inf,inq[s]=1,d[s]=0,push(s); while(qlast<=qfront) { register int u=q[qlast]; for (int i=head[u];i;i=e[i].next) { register int v=e[i].v; if(e[i].cap>e[i].flow&&d[v]>d[u]+e[i].cost) { p[v]=i; a[v]=min(a[u],e[i].cap-e[i].flow); d[v]=d[u]+e[i].cost; if (!inq[v]) { push(v); inq[v]=1; } } } inq[u]=0; pop(); } if (d[t]==inf)return false; cost+=1ll*d[t]*a[t]; flow+=a[t]; for (register int u=t;u!=s;u=e[p[u]].u) { e[p[u]].flow+=a[t]; e[p[u]^1].flow-=a[t]; } return true;}int mcmf(ll &cost){ register int flow=0; cost=0; while(spfa(flow,cost)); return flow;}int main(){ te=1; memset(inq,0,sizeof(inq)); memset(head,0,sizeof(head)); n=F(); for(register int i=1;i<=n;++i) val[i]=F(); s=(n<<1)+1,t=s+1; c=F(),tf=F(),cf=F(),ts=F(),cs=F(); for(register int i=1;i<=n;++i) { insert(s,i,val[i],0); insert(i+n,t,val[i],0); insert(s,i+n,inf,c); if (i<n)insert(i,i+1,inf,0); if (i+tf<=n)insert(i,i+tf+n,inf,cf); if (i+ts<=n)insert(i,i+ts+n,inf,cs); }// for (int i=2;i<=te;i+=2)// cout<<e[i].u<<' '<<e[i].v<<' '<<e[i].cap<<' '<<e[i].cost<<endl; ll cost; mcmf(cost); cout<<cost;}新闻热点
疑难解答
