神建模…我真是太菜了…

懵逼的 题目

1070: [SCOI2007]修车

2879: [Noi2012]美食节

扯淡的 题解

我内心: 这玩意咋做啊qwqwqwqwqwq, 之前的东西会对后面的边权造成影响啊qwqwqwqwqwq

然后翻题解…王gay梁A了… AHmhr A了…xMinh A了…REfun A了…

…你们都太强了 Orzzzzzz

前面会对后面造成影响那我倒过来连边不就行了…

设 第$j$盘菜是第$i$个人做的倒数第$k$盘菜, 那么这盘菜对答案的影响就是后面的$k$个人, 影响的总时间是$k \cdot time_{i, j}$

然后好啦

  • 拆点: 把每一个厨师拆成$\sum_j^n p_j$个点$b_{i, k}$, 代表第$i$个厨师做倒数第$k$盘菜

  • 连边:

    • $S$向所有的菜$c_i$连边$cost = 0, cap = (c_i$的需求量$)$
    • $c_j$向$b_{i, k}$连边, $cost = k \cdot time_{i, j}, cap = 1$
    • $b_{i, k}$向$T$连边, $cost = 0, cap = 1$

没了?

没了

你用这种方法做美食节的时候…你会发现你T的很惨啊…Emmmmmmmm…我们有一种奇妙的优化方法…

我们发现这个边数太多了…然而每一次曾广只会用到$3$条边…$spfa$的复杂度就爆炸了…

考虑怎么缩减边数…

你跑$spfa$肯定是先跑费用最小的边…而如果边$c_j \to b_{i, k + 1}$符合要求, 而且$(c_j \to b_{i, k}).cap > (c_j \to b_{i, k}).flow$时, 肯定是要跑$c_j \to b_{i, k}$的…

也就是说, 如果$c_j\to b_{i, k}$没有满流, 我们是没有必要加$c_j \to b_{i, k + 1}$这条边的…我们就可以在每一次增广后才加入对应的边, 这样就保证了整个图的边数都在一个可以接受的范围内

复杂度? $\mathrm O($跑的过$)$…

srO 舒老师

srO 不认识的大佬

沙茶的 代码

修车

他bzoj这个题时限$1s$感觉很不资瓷啊…没(懒得)

你以为你bzoj的测评姬速度能和别的oj比还是咋的, 还™搞总时限$1s$

/**************************************************************
    Problem: 1070
    User: Cansult
    Language: C++
    Result: Time_Limit_Exceed
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define INF (0X7FFFFFFF)
#define MAXC (100)
#define rev(a) ((a) ^ 1)
#define bh(i, j) ((((i) - 1) * MAXC) + j)
#define ca(i) (i + 90000)
#define DD double
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
    int from, to, next, cap, flow, cost;
    edg() {}
    edg(int fr, int dqt, int ne, int ca, int co): from(fr), to(dqt), next(ne), cap(ca), flow(0), cost(co) {}
}b[MAXM << 1];
int g[MAXN], cntb = -1, n, m, gg[MAXC][MAXC], pre[MAXN], ans;
void adn(int from, int to, int cap, int cost)
{
    b[++cntb] = edg(from, to, g[from], cap, cost);
    g[from] = cntb;
}
int spfa()
{
    int dis[MAXN], a[MAXN];
    bool inq[MAXN];
    memset(inq, false, sizeof(inq));
    memset(dis, 0x7f, sizeof(dis));
    memset(a, 0, sizeof(a));
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    a[s] = INF;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        inq[dq] = false;
        for (int i = g[dq]; ~i; i = b[i].next)
            if (dis[b[i].to] > dis[dq] + b[i].cost && b[i].cap > b[i].flow)
            {
                a[b[i].to] = min(a[dq], b[i].cap - b[i].flow);
                pre[b[i].to] = i;
                dis[b[i].to] = dis[dq] + b[i].cost;
                if (!inq[b[i].to])
                    inq[b[i].to] = true, q.push(b[i].to);
            }
    }
    return a[t];
}
void solve()
{
    while (true)
    {
        int zl = spfa();
        if (!zl)    break;
        for (int i = t; i != s; i = b[pre[i]].from)
            /*printf("from: %d, to: %d, cost: %d, flow: %d\n", b[pre[i]].from, b[pre[i]].to, b[pre[i]].cost, b[pre[i]].flow), */b[pre[i]].flow += zl, b[rev(pre[i])].flow -= zl, ans += zl * b[pre[i]].cost; // Emmmm怎么加成流量了...
//      puts("-----------");
    }
}
void init()
{
    for (int i = 1; i <= m; i++)
        adn(s, ca(i), 1, 0), adn(ca(i), s, 0, 0);
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
            adn(bh(i, j), t, 1, 0), adn(t, bh(i, j), 0, 0);
    for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
    for (int k = 1; k <= m; k++)
        adn(ca(i), bh(j, k), 1, gg[j][i] * k), adn(bh(j, k), ca(i), 0, -gg[j][i] * k);
}
int main()
{
//    cout << "Hello world!" << endl;
//  freopen("in.in", "r", stdin);
    memset(g, -1, sizeof(g));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &gg[j][i]);
    init();
    solve();
    printf("%.2lf", (DD)ans / m);
    return 0;
}

/*
3 9
42 2 53
16 66 94
37 55 99
77 79 11
9 2 95
19 49 10
5 19 91
36 14 95
100 61 54

23.78
*/

美食节

其实这个实现还是有一些细节

如果你一开始就把所有的$b_{i, k}$与$T$连上边了, 你的常数就炸了…稳定$1.4s$…

所以要把$b_{i, k}\to T$的连边和$c_j \to b_{i, k}$的连边放在一起…

/**************************************************************
    Problem: 2879
    User: Cansult
    Language: C++
    Result: Accepted
    Time:7108 ms
    Memory:14932 kb
****************************************************************/

/*
费用流
我猜...对于每一个厨师来说, 应该先放用时小的..
每一道菜我是不是可以多连几条边然后赋边权啥的...
我是不是可以...按照边权, 一层一层的加...
写一写?

Naive!
...
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define INF (0x7fffffff)
#define MAXC (800 + 5)
#define MAXH (100 + 5)
#define rev(a) ((a) ^ 1)
#define ca(i) (90000 + i)
#define bh(i, j) ((i) * MAXC + (j))
#define cint const int
#define rint register int
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
    int from, to, next, cap, flow, cost;
    edg() {}
    edg(cint fr, cint dqt, cint ne, cint ca, cint co): from(fr), to(dqt), next(ne), cap(ca), flow(0), cost(co) {}
}b[MAXM];
int g[MAXN], cntb = -1, n, m, cnt[MAXC], dqch, ans, fans, gg[MAXH][MAXC], totp, pre[MAXN];
inline void adn(cint from, cint to, cint cap, cint cost)
{
    b[++cntb] = edg(from, to, g[from], cap, cost);
    g[from] = cntb;
}
inline int min(const int x, const int y)
{
    if (x > y)
        return y;
    else
        return x;
}
int spfa()
{
    int dis[MAXN], a[MAXN];
    bool inq[MAXN];
    queue<int> q;
    memset(dis, 0x7f, sizeof(dis));
    memset(inq, false, sizeof(inq));
    a[t] = 0;
    a[s] = INF;
    dis[s] = 0;
    q.push(s);
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        inq[dq] = false;
        for (rint i = g[dq]; ~i; i = b[i].next)
            if (dis[b[i].to] > dis[dq] + b[i].cost && b[i].cap > b[i].flow)
            {
                dis[b[i].to] = dis[dq] + b[i].cost;
                a[b[i].to] = min(a[dq], b[i].cap - b[i].flow);
                pre[b[i].to] = i;
                if(!inq[b[i].to])
                    q.push(b[i].to), inq[b[i].to] = true;
            }
    }
    return a[t];
}
int solve()
{
    cint zl = spfa();
    fans += zl;
    for (rint i = t; i != s; i = b[pre[i]].from)
    {
        if (b[pre[i]].from < 90000 && b[pre[i]].to == t)
            dqch = b[pre[i]].from / MAXC;
        b[pre[i]].flow += zl, b[rev(pre[i])].flow -= zl;
        ans += zl * b[pre[i]].cost;
    }
    return dqch;
}
void qwq()
{
    for (rint i = 1; i <= m; i++)
    for (rint j = 1; j <= n; j++)
        adn(ca(j), bh(i, cnt[i] + 1), 1, gg[i][j] * (cnt[i] + 1)), adn(bh(i, cnt[i] + 1), ca(j), 0, -gg[i][j] * (cnt[i] + 1));
    for (int i = 1; i <= m; i++)
        adn(bh(i, cnt[i] + 1), t, 1, 0), adn(t, bh(i, cnt[i] + 1), 0, 0);
    /*for (rint i = 1; i <= m; i++)
    for (rint j = 1; j <= totp; j++)
        adn(bh(i, j), t, 1, 0), adn(t, bh(i, j), 0, 0);*/
    while (fans < totp)
    {
        cint i = solve();
        ++cnt[i];
        for (rint j = 1; j <= n; j++)
            adn(ca(j), bh(i, cnt[i] + 1), 1, gg[i][j] * (cnt[i] + 1)), adn(bh(i, cnt[i] + 1), ca(j), 0, -gg[i][j] * (cnt[i] + 1));
        adn(bh(i, cnt[i] + 1), t, 1, 0), adn(t, bh(i, cnt[i] + 1), 0, 0);
    }
}
inline int read()
{
    rint re = 0, f = 1;
    register char x = 0;
    while (x < '0' || x > '9')
    {
        if (x == '-')
            f = -1;
        x = getchar();
    }
    while (x >= '0' && x <= '9')
        re = (re << 1) + (re << 3) + x - '0', x = getchar();
    return re * f;
}
int main()
{
    memset(g, -1, sizeof(g));
//  scanf("%d%d", &n, &m);
    n = read(), m = read();
    for (rint i = 1, srx; i <= n; i++)
        /*scanf("%d", &srx), */srx = read(), adn(s, ca(i), srx, 0), adn(ca(i), s, 0, 0), totp += srx;
    for (rint i = 1; i <= n; i++)
    for (rint j = 1; j <= m; j++)
        gg[j][i] = read();
    //      scanf("%d", &gg[j][i]);
    qwq();
    printf("%d", ans);
    return 0;
}

/*
3 2
3 1 1
5 7
3 6
8 9
*/

By 沙茶 Cansult