Post 44

Veröffentlicht am

这笔记本真差劲。。比起surface book差了老远。。

我到现在除了能在本地用Vim写个程序以外还啥也不能干。。。

明天最后试试Win10能不能装成功，反正win7要想装成功非常困难。

培训之前肯定把这事弄好。

Dinic

算法实现很简单，主要是想明白其正确性，由于每次都会分层，所以最后还是能找到所有的增广路，根据增广路定理最后得到的就是最大流。

我不明白为啥分了层就优化到$O(n^2m)$了。

还加了个多路增广，懒得加当前弧优化了。

Code：

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#define maxn 30005
#define maxm 100005
#define INF 0x7ffffff
int hd[maxn] , ct = 1 , MaxFlow , n , m , dep[maxn] ,  s , t;
bool vs[maxn];
struct edge{
    int nxt , to , dis;
}e[maxm<<1];

inline void add(int x, int y , int d)
{
    e[++ct] = (edge){hd[x],y,d};
    hd[x] = ct;
}

inline bool bfs()
{
    for(int i = 1 ; i <= n ; ++i)	dep[i] = INF;
    dep[s] = 0;
    std::queue<int> q;
    q.push(s);
    for( ; q.size() ; q.pop())
    {
        int k = q.front();
        for(int i = hd[k] ; i ; i = e[i].nxt)
            if(dep[e[i].to] == INF && e[i].dis)	dep[e[i].to] = dep[k] + 1 , q.push(e[i].to);
    }
    return dep[t] != INF;
}

int dfs(int u , int cfw)
{
    if(u == t || !cfw) return cfw;
    int flow = 0 , f;
    for(int i = hd[u] ; i ; i = e[i].nxt)
    {
        int v = e[i].to;
        if(dep[v] == dep[u] + 1 && (f = dfs(v , std::min(cfw , e[i].dis))))
        {
            flow += f;
            cfw -= f;
            e[i].dis -= f , e[i^1].dis += f;
            if(!cfw) break;
        }
    }
    return flow;
}

inline int Dinic()
{
    int f;
    for( ; bfs() ; MaxFlow += dfs(s,INF));
    return MaxFlow;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i = 1 ; i <= m ; ++i)
    {
        int x , y , d;
        scanf("%d%d%d",&x,&y,&d);
        add(x,y,d) , add(y,x,0);
    }
    printf("%d\n",Dinic());
}

然后顺便学习了最小费用最大流，用的EK+SPFA.

没看懂DIjkstra的势是怎么证明正确性的然后就没学

其实思想很简单，我们始终找源点到汇点的在边有流量的情况下(不管多少)的最短路，然后更新。直到没有增广路。由增广路定理可知此时达到最大流，由于一直走的最短路寻找增广路，所以由贪心可知（很简单的反证）此时费用达到最小。

Code：

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#define maxn 5005
#define maxm 50005
#define INF 0x7ffffff
int hd[maxn] , n , m , s , t , ct = 1, fw[maxn] , d[maxn] , pre[maxn] , ep[maxn] , MxFw;
long long MnCo;
bool vis[maxn];
struct edge{
    int next , to , fw , dis;
}e[maxm<<1];

inline void add(int x , int y , int fw , int dis)
{
    e[++ct] = (edge){hd[x],y,fw,dis};
    hd[x] = ct;
}

inline bool bfs()
{
    std::queue<int> q;
    std::memset(d,0x7f,sizeof(d));
    std::memset(fw,0x7f,sizeof(fw));
    std::memset(vis,false,sizeof(vis));
    vis[s] = true , d[s] = 0 , pre[t] = -1;
    q.push(s);
    for(int k ; q.size() ; q.pop())
    {
        k = q.front();
        vis[k] = false;
        for(int i = hd[k] ; i ; i = e[i].next)
        {
            int v = e[i].to;
            if(d[k] + e[i].dis < d[v] && e[i].fw)
            {
                fw[v] = std::min(fw[k] , e[i].fw);
                pre[v] = k , ep[v] = i;
//				if(~pre[t]) return true;
                d[v] = d[k] + e[i].dis;
                if(!vis[v])
                    vis[v] = true , q.push(v);
            }
        }
    }
    return (bool)~pre[t];
}

inline void mcmf()
{
    for( ; bfs() ; )
    {
        int now = t;
        MxFw += fw[t];
        MnCo += fw[t] * d[t];
        while(now != s)
        {
            e[ep[now]].fw -= fw[t];
            e[ep[now]^1].fw += fw[t];
            now = pre[now];
        }
    }
}

int main()
{
//	freopen("data.out.txt","r",stdin);
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i = 1 ; i <= m ; ++i)
    {
        int x , y , z, d;
        scanf("%d%d%d%d",&x,&y,&z,&d);
        add(x,y,z,d) , add(y,x,0,-d);
    }
    mcmf();
    printf("%d %lld\n",MxFw , MnCo);
}

好像费用流有更快的算法，不过网络流最重要的又不是写板子。。。

接下来可能会学完左偏树，LCT，真希望不要退役啊。

不退役我还会认认真真学完算导和具体数学。可能还会在多学一点数学知识。

（退役了补文化课也不是很糟糕的感觉