遇到这种题就只能猜证结合，构图瞎蒙
upd:这道题还是非常厉害的我才没有因为day3被卡线要去听菜鸡大讲堂diss叫我讲这题的主讲师兄
考虑到主要要算的是最小费用，而网络流是否满流成了一个棘手的问题（一共用的毛巾并不确定）
但是确定的是每天要用的毛巾数，我们可以拆点，一个表示当天的用下来的旧毛巾，然后去变成新的，一个表示当天新毛巾，到ed可以了，st和ed各连一个流量为当天要用的，相当于充当了一个传递的功能
#include#include #include #include #include #include using namespace std;const int inf=99999999;struct node{ int x,y,c,d,next,other;}a[2100000];int len,last[2100000];void ins(int x,int y,int c,int d){ int k1,k2; k1=++len; a[len].x=x;a[len].y=y;a[len].c=c;a[len].d=d; a[len].next=last[x];last[x]=len; printf("%d %d %d %d\n",x,y,c,d); k2=++len; a[len].x=y;a[len].y=x;a[len].c=0;a[len].d=-d; a[len].next=last[y];last[y]=len; a[k1].other=k2; a[k2].other=k1;}int n,st,ed,ans;int list[21000];bool v[21000];int d[21000],cc[21000],pre[21000];bool spfa(){ memset(d,63,sizeof(d));d[st]=0; memset(cc,0,sizeof(cc));cc[st]=inf; memset(v,false,sizeof(v));v[st]=true; int head=1,tail=2;list[1]=st; while(head!=tail) { int x=list[head]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(d[y]>d[x]+a[k].d&&a[k].c>0) { d[y]=d[x]+a[k].d; cc[y]=min(cc[x],a[k].c); pre[y]=k; if(v[y]==false) { v[y]=true; list[tail]=y; tail++;if(tail==20500)tail=1; } } } v[x]=false; head++;if(head==20500)head=1; } if(d[ed]>=inf)return false; else { ans+=cc[ed]*d[ed]; int y=ed; while(y!=0) { int k=pre[y]; a[k].c-=cc[ed]; a[a[k].other].c+=cc[ed]; y=a[k].x; } return true; }}int main(){ int A,B,f,fa,fb,x; scanf("%d%d%d%d%d%d",&n,&A,&B,&f,&fa,&fb);st=2*n+1,ed=2*n+2; len=0;memset(last,0,sizeof(last)); for(int i=1;i<=n;i++) { scanf("%d",&x); ins(st,i,x,0); ins(i+n,ed,x,0); ins(st,i+n,inf,f); } for(int i=1;i