[网络流24题]餐巾计划问题

题目

链接

思路

1. 洗了的餐巾+买的餐巾=用的餐巾=r[ i ]，洗的餐巾一定会用（废话）

2. 第i天用的餐巾可以通过清洗操作给之后i+快洗，为了减少连边的数量，可以通过延期，让餐巾当它到要用的那天之前再洗

连边

1. 左边的一排\(x_i\)表示到今天为止有的脏餐巾数（可以将脏餐巾转移到之后），右边一排\(y_i\)表示这天要用的餐巾数，显然，\(x_i\)和\(y_i\)都有增加\(r_i\)，\(x_i\)增加\(r_i\)表示这一天之后多得到了\(r_i\)的脏餐巾，\(y_i\)增加\(r_i\)表示这一天要用\(r_i\)的餐巾

2. \(s\)->\(x_i\)，\(y_i\)->\(t\)，容量为\(r_i\)，权值为0

3. \(s\)->\(y_i\)，容量为INF，权值为\(p\)，表示买餐巾

4. \(x_i\)->\(x_{i+1}\)，容量为INF，权值为0，表示延期

5. \(x_i\)->\(y_{i+m}\)，容量为INF，权值为\(f\)，表示快洗

6. \(x_i\)->\(y_{i+n}\)，容量为INF，权值为\(s\)，表示慢洗

然后跑最小费用流即可，由于中间连的INF边，\(y_i\)->\(t\)的边一定可以满流

Code:

#include<bits/stdc++.h>
#define N 5005
#define M 500005
using namespace std;
typedef long long ll;
const ll INF = 10000000000000000;
int n,s,t;
ll r[N],p,fas,fascost,slo,slocost;
int pre[N],preedge[N];
ll dis[N],flow[N];
ll mincost,maxflow;
bool exist[N];

struct Edge
{
    int next,to;
    ll flow,dis;
}edge[M<<1];int head[N],cnt=1;
void add_edge(int from,int to,ll flow,ll dis)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    edge[cnt].flow=flow;
    edge[cnt].dis=dis;
    head[from]=cnt;
}
void add(int from,int to,ll flow,ll dis)
{
    add_edge(from,to,flow,dis);
    add_edge(to,from,0,-dis);
}
template <class T>
void read(T &x)
{
    char c;int sign=1;
    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
    while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}
bool spfa(int s,int t)
{
    memset(dis,100,sizeof(dis));
    memset(flow,100,sizeof(flow));
    memset(exist,0,sizeof(exist));
    queue<int> q;
    pre[t]=-1; exist[s]=1; dis[s]=0; q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();exist[u]=0;
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].to;
            if(edge[i].flow>0&&dis[v]>dis[u]+edge[i].dis)
            {
                dis[v]=dis[u]+edge[i].dis;
                flow[v]=min(edge[i].flow,flow[u]);
                pre[v]=u;
                preedge[v]=i;
                if(!exist[v])
                {
                    exist[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return pre[t]!=-1;
}
void MCMF()
{
    while(spfa(s,t))
    {
        maxflow+=flow[t];
        mincost+=flow[t]*dis[t];
        int now=t;
        while(now!=s)
        {
            edge[preedge[now]].flow-=flow[t];
            edge[preedge[now]^1].flow+=flow[t];
            now=pre[now];
        }
    }
}
int main()
{
    read(n);
    s=2*n+1;t=s+1;
    for(int i=1;i<=n;++i) read(r[i]);
    read(p);read(fas);read(fascost);read(slo);read(slocost);
    for(int i=1;i<=n;++i)
    {
        add(s,i,r[i],0);
        add(i+n,t,r[i],0);
        if(i+1<=n) add(i,i+1,INF,0);
        add(s,i+n,INF,p);
        if(i+fas<=n) add(i,i+fas+n,INF,fascost);
        if(i+slo<=n) add(i,i+slo+n,INF,slocost);
    }
    MCMF();
    cout<<mincost<<endl;
    return 0;
}

[网络流24题]餐巾计划问题

原文：https://www.cnblogs.com/Chtholly/p/11295724.html