= =感覺這兩天做的最有質量的一道題，盡管以前做過但還是想了一會，建圖建的很巧妙. 首先我們很容易可以看出這是一個費用流，然后我們先拆點，把每天分成兩個點，一個表示干凈的餐巾，一個表示臟的餐巾，這里表示為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;}新聞熱點
疑難解答
