餐巾计划问题
前言
zkw真滴快！
题目
洛谷
洛谷(加强版)
讲解
刚开始思考这道题的时候，我试图解决干净餐巾->脏餐巾 和 脏餐巾->干净餐巾的转移，发现不会。然后各种讨论快洗慢洗关系，发现有单调性/凸性，可能可以二分/三分，但还是不会，于是自闭。
显然我们不能把干净餐巾和脏餐巾混为一谈，所以我们拆点，可以视作将一天拆为早上与晚上，早上收到干净餐巾并使用餐巾，晚上获得脏餐巾，洗餐巾可以转移到某一天的早上。
那么我们怎么强制早上使用餐巾并转移到晚上呢？
拆一下，我们可以看成是早上一定要使用干净餐巾，晚上一定要获得脏餐巾。
所以我们可以直接从早上向汇点连边，表示使用餐巾，源点向晚上连边表示获得餐巾。
剩下的连边就很好解决了。
- 早上向汇点连边，表示使用餐巾。
- 源点向晚上连边，表示获得餐巾。
- 汇点向早上连边，表示购买餐巾。
- 头天晚上向下一天晚上连边，表示懒狗不想洗餐巾。
- 晚上向某个白天连边，表示洗餐巾。
如果用多路增广的 zkw费用流，可以直接把 \(N\le 2\times 10^5\) 的加强版冲过去，加强版的正解应该是我之前思考的讨论+二分/三分，这里不做拓展。
代码
加强版
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 400005;
const int INF = 0x3f3f3f3f;
int days,p,qd,qc,sd,sc;//quick days; quick cost; slow..
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int head[MAXN],tot = 1,cur[MAXN];
struct edge{
int v,w,c,nxt;
}e[MAXN<<3];
void Add_Edge(int u,int v,int w,int c){
e[++tot] = edge{v,w,c,head[u]};
head[u] = tot;
}
void Add_Double_Edge(int u,int v,int w,int c){
Add_Edge(u,v,w,c);
Add_Edge(v,u,0,-c);
}
int dis[MAXN],maxflow;
LL mincost;
bool inq[MAXN],vis[MAXN];
bool bfs(int S,int T){
for(int i = 1;i <= T;++ i) dis[i] = INF;
queue q; q.push(S); dis[S] = 0;
while(!q.empty()){
int x = q.front(); q.pop(); inq[x] = 0;
for(int i = head[x],v; i ;i = e[i].nxt)
if(e[i].w && dis[x] + e[i].c < dis[v = e[i].v]){
dis[v] = dis[x] + e[i].c;
if(!inq[v]) inq[v] = 1,q.push(v);
}
}
return dis[T] < INF;
}
int dfs(int x,int flow,int T){
if(x == T) return flow;
int ret = 0; vis[x] = 1;
for(int &i = cur[x],v; i ;i = e[i].nxt)
if(e[i].w && dis[x] + e[i].c == dis[v = e[i].v] && !vis[v]){
int dz = dfs(v,Min(flow-ret,e[i].w),T);
e[i].w -= dz; e[i^1].w += dz;
if((ret += dz) == flow) break;
}
vis[x] = 0;
return ret;
}
void MFMC(int S,int T){
while(bfs(S,T)){
for(int i = 1;i <= T;++ i) cur[i] = head[i];
int ret = dfs(S,INF,T);
maxflow += ret; mincost += 1ll * ret * dis[T];
}
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
days = Read(); qd = Read(); sd = Read(); qc = Read(); sc = Read(); p = Read();
int S = days<<1|1,T = S+1,sx = days<<1;
for(int i = 1;i <= days;++ i){
int nd = Read(),day = (i<<1)-1,night = day+1;
Add_Double_Edge(day,T,nd,0);//use napkins
Add_Double_Edge(S,night,nd,0);//gain dirty napkins
Add_Double_Edge(S,day,INF,p);//purchase
if(night+2 <= sx) Add_Double_Edge(night,night+2,INF,0);//lazy dog
if(day+(qd<<1) <= sx) Add_Double_Edge(night,day+(qd<<1),INF,qc);//quick wash
if(day+(sd<<1) <= sx) Add_Double_Edge(night,day+(sd<<1),INF,sc);//slow wash
}
MFMC(S,T);
Put(mincost,'\n');
return 0;
}