写网络流写的头昏脑涨QAQ大概还是太菜了

比较有趣的建图题

对于每一个点拆点拆成早晨和晚上分别为 i 和 i'

1. s -> i (r,p) 每天早晨可以买最多r条新餐巾 一条p分

2. s -> i' (r,0) 每天用剩下r条脏餐巾 没有代价

3. i -> t (r,0) 每天要用r条干净餐巾 没有代价

4. i' -> i+m (inf,f) 脏毛巾送到快洗店 洗干净送回来是第i+m天 每条花费代价f分

5. i' -> i+n (inf,s) 脏毛巾送到慢洗店 洗干净送回来是第i+n天 每条花费代价s分

6. i' -> (i+1)' (inf,s) 每条脏毛巾留到第二天再处理 没有代价

神建图题QAQ 天真的我以为n^2的图也可以跑的QAQ 难受的一批

果然脑子题还是不适合我

附代码。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define inf 2002122500#define mxn 2010#define ll long longusing namespace std;struct edge{int to,lt,fr;ll f,c;}e[mxn*40];queue
         
           que;int in[mxn*4];bool vis[mxn*4];int cnt=1,nn,s,t,from[mxn*4];ll dis[mxn*4];void add(int x,int y,ll f,ll c){ e[++cnt].to=y;e[cnt].lt=in[x];e[cnt].fr=x; e[cnt].f=f;e[cnt].c=c;in[x]=cnt; e[++cnt].to=x;e[cnt].lt=in[y];e[cnt].fr=y; e[cnt].f=0;e[cnt].c=-c;in[y]=cnt;}bool spfa(){ for(int i=1;i<=nn;i++) dis[i]=inf,vis[i]=0; dis[s]=0;vis[s]=1;que.push(s); while(!que.empty()) { int x=que.front();que.pop(); for(int i=in[x];i;i=e[i].lt) { int y=e[i].to; if(dis[y]>dis[x]+e[i].c&&e[i].f) { dis[y]=dis[x]+e[i].c;from[y]=i; if(!vis[y]) que.push(y),vis[y]=1; } } vis[x]=0; } return dis[t]