Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

翻车笔记 [SCOI2007]修车 + [Noi2012]美食节 [网络流, 清奇脑回路, 翻车]

Posted on Edited on In

神建模...我真是太菜了...

懵逼的 题目

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(\)跑的过\()\)...

沙茶的 代码

修车

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/**************************************************************
    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}\)的连边放在一起...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/**************************************************************
    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