网络流建模方法三描述每一个决策的问题， 其实网络流一直都在做这个事，去描述决策的问题， 把他称之为一种建模方法似乎有一点过分，或者应该将其称之为一种题型，一种描述决策的题型吧！还是先说题目 洛谷P1251
题目描述
一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 ii 天需要 r_ir i块餐巾( i=1,2,…,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 pp 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 nn 天(n>mn>m),其费用为 ss 分(s<fs<f)。每天结束时,餐厅必须决定将多少块脏的餐巾送到快洗部,多少块餐巾送到慢洗部,以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和,要满足当天的需求量。试设计一个算法为餐厅合理地安排好 NN 天中餐巾使用计划,使总的花费最小。编程找出一个最佳餐巾使用计划。
输入格式
由标准输入提供输入数据。文件第 1 行有 1 个正整数 NN，代表要安排餐巾使用计划的天数。
接下来的 NN 行是餐厅在相继的 NN 天里,每天需用的餐巾数。
最后一行包含5个正整数p,m,f,n,sp,m,f,n,s。pp 是每块新餐巾的费用; mm 是快洗部洗一块餐巾需用天数; ff 是快洗部洗一块餐巾需要的费用; nn 是慢洗部洗一块餐巾需用天数; ss 是慢洗部洗一块餐巾需要的费用。
输出格式
将餐厅在相继的 N 天里使用餐巾的最小总花费输出
输入
3
1 7 5
11 2 2 3 1
输出
134
<mark>说明/提示</mark>
N<=2000

ri<=10000000

p,f,s<=10000

时限4s

---------------------------------------------------------------------------------------------------------------------------------------
<mark>这道题目我们这样建模，我们依据题意把每天分别拆开拆成早晨和晚上（为啥这么拆？因为依据题意我们 很容易发现 一天有两种状态， 分别是早晨收到新的餐巾，和晚上把餐巾拿去清洗或者留到下一天晚上）那么我们把原点连接晚上表示每天晚上会获得x份脏的餐巾，把汇点与早晨相连表示每天要提供x份餐巾够用，接下来我们来处理脏的餐巾，依据题意脏的餐巾有如下几种处理方式：
1.留到第二天晚上， 这样我们就把当天晚上和下一天晚上相连接，流量是INF，费用为0
2.快洗，我们把当天晚上接受到的脏餐巾和快洗后的早晨想连接，流量为INF，费用为0
3.慢洗，我们把当天晚上接受到的脏餐巾和慢洗后的早晨相连接，流量为INF，费用为0
建图是一定要切记判断快洗，慢洗，留到第二天，是否还在N的范围内，
最后还有买新的餐巾的方法不要忘记</mark>
---------------------------------------------------------------------------------------------------------------------------------------

AC代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

struct Edge
{
    int to, w, f, next;
}edg[MAXN];

int head[MAXN], pre[MAXN], dis[MAXN], vis[MAXN], flow[MAXN], cnt = 0, last[MAXN];

void init()
{
    memset(head, -1, sizeof(head));
    cnt = 0;
}

void Add_edge(int u, int v, int w, int f)
{
    edg[cnt].w = w;
    edg[cnt].to = v;
    edg[cnt].f = f;
    edg[cnt].next = head[u];
    head[u] = cnt++;
    edg[cnt].w = 0;
    edg[cnt].to = u;
    edg[cnt].f = -f;
    edg[cnt].next = head[v];
    head[v] = cnt++;
}

bool SPFA(int s, int t)
{
    queue<int> q;
    memset(dis, INF, sizeof(dis));
    memset(flow, INF, sizeof(flow));
    dis[s] = 0;
    pre[t] = 0;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        vis[u] = 0;
        for(int i = head[u]; i != -1; i = edg[i].next)
        {
            int v = edg[i].to;
           // int w = edg[i].w;
            if(edg[i].w && dis[v] > dis[u] + edg[i].f)
            {
                dis[v] = dis[u] + edg[i].f;
                pre[v] = u;
                last[v] = i;
                flow[v] = min(flow[u], edg[i].w);
                if(!vis[v])
                {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return pre[t];
}

int Mincost(int s, int t)
{
    int mincost = 0;
    while(SPFA(s, t))
    {
        mincost += dis[t] * flow[t];
        int now = t;
        while(now != s)
        {
            edg[last[now]].w -= flow[t];
            edg[last[now]^1].w += flow[t];
            now = pre[now];
        }
    }
    return mincost;
}

int main()
{
    int N, x, p, m, f, n, S;
    scanf("%d", &N);
    init();
    long long s = 0, t = N * 2 + 1;
    for(int i = 1; i <= N; ++i)
    {
        scanf("%d", &x);
        Add_edge(s, i, x, 0);
        Add_edge(i + N, t, x, 0);
    }
    scanf("%d %d %d %d %d", &p, &m, &f, &n, &S);
    for(int i = 1; i <= N; ++i)
    {
        if(i + 1 <= N) Add_edge(i, i + 1, INF, 0);//留到第二天晚上
        if(i + m <= N) Add_edge(i, i + N + m, INF, f);//快洗
        if(i + n <= N) Add_edge(i, i + N + n, INF, S);//慢洗
        Add_edge(s, i + n, INF, p);//购买新的餐巾
    }
    printf("%d\n", Mincost(s, t));
}