网络流2423(没有那道不可做题)题解题报告

(没事, LOJ也只有23道

Table of Contents

  1. Overview
  2. LOJ 6000, 二分图匹配
  3. LOJ 6001, 最大权闭合子图
  4. LOJ 6002, 最小路径覆盖
  5. LOJ 6003, 最大流
  6. LOJ 6004, 最大流.
  7. LOJ 6005, 最大流
  8. LOJ 6006, 最大流
  9. LOJ 6007,最小割
  10. LOJ 6008, 费用流
  11. LOJ 6009, 状态压缩
  12. LOJ 6010, 费用流
  13. LOJ 6011, 费用流
  14. LOJ 6012, 费用流
  15. LOJ 6013, 费用流
  16. LOJ 6014, 费用流
  17. LOJ 6015, 最大流
  18. LOJ 6121, ~~状压分层图最短路
  19. LOJ 6122, 最大流
  20. LOJ 6223, 分层图最短路
  21. LOJ 6224, 费用流
  22. LOJ 6225, 费用流
  23. LOJ 6226, 最小割
  24. LOJ 6227, 费用流

Overview

常见模型:

最大流

最小割 转 最大流

最小费用最大流

状态压缩, 分层图最短路

LOJ 6000, 二分图匹配

二分图匹配. 嗯.

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

using std::min;
using std::max;
using std::memset;

const int maxn = 105;

struct edge{
    int to,nxt;
}e[maxn*maxn];
int lnk[maxn],edgenum;
int n,m,match[maxn],vis[maxn],u,v;

void add(int bgn,int end)
{
    e[++edgenum].to = end;
    e[edgenum].nxt = lnk[bgn];
    lnk[bgn] = edgenum;
}
bool dfs(int x)
{
    for(int p=lnk[x];p;p=e[p].nxt){
        int y=e[p].to;
        if(!vis[y]){
            vis[y]=1;
            if(!match[y]||dfs(match[y])){
                match[y]=x;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int ans = 0;
    scanf("%d%d",&m,&n);
    while(scanf("%d%d",&u,&v)&&u != -1&&v != -1)
    {
        add(u,v);
    }
    for(int i = 1; i <= m; ++i)
    {
        memset(vis,0,sizeof(vis));
        if(dfs(i))ans++;
    }
    printf("%d\n",ans);
    for(int i = m + 1 ; i <= n; ++i)
    {
        if(match[i])printf("%d %d\n",match[i],i);
    }
    return 0;
}

LOJ 6001, 最大权闭合子图

正权连源, 负权连汇, 有边连$\infty$.

正权和 - 最小割 = 最大权值和.

选的点是 $S$ 集.

来自Alan_cty的slide

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<bitset>
#include<cstdlib>
using namespace std;

const int maxn = 105;
const int inf_ = 0x3f3f3f3f;

struct edge
{
    int to, nxt, v;
}e[maxn * maxn << 3];
int v[maxn], tc[maxn], n, m, s, t, ptr;
int level[maxn], lnk[maxn];
vector<int> ndd[maxn], expr;
queue<int> q;
bitset<maxn> use, exec;
char str[10000];

inline void add(int bgn, int end, int val)
{
    e[ptr].to = end; e[ptr].nxt = lnk[bgn]; e[ptr].v = val; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].nxt = lnk[end]; e[ptr].v = 0; lnk[end] = ptr; ptr++;
}
inline bool bfs()
{
    memset(level, 0, sizeof level);
    q.push(s); level[s] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].v > 0 && !level[y])
            {
                level[y] = level[u] + 1;
                //printf("dep %d = %d\n", y, level[y]);
                q.push(y);
            }
        }
    }
    //printf("%d\n", level[t]);
    return level[t] != 0;
}
int dfs(int x, int fl)
{
    //printf("now %d\n", fl);
    if(x == t) return fl;
    //puts("dfs");printf("%d\n", x);
    //Sleep(1000);
    for(int p = lnk[x]; ~p; p = e[p].nxt)
    {
        int y = e[p].to; //printf("to %d\n", y);
        if(level[y] == level[x] + 1 && e[p].v)
        {
            int delta = dfs(y, min(e[p].v, fl));
            //printf("delta%d\n", delta);
            if(delta > 0)
            {
                //if(x == s) expr.push_back(y);
                e[p].v -= delta;
                e[p^1].v += delta;
                return delta;
            }
        }
    }	
    return 0;
}
int dinic()
{
    int ret = 0;
    while(bfs())
    {
        while(int delta = dfs(s, inf_))
            ret += delta;
    }
    return ret;
}

int main()
{
    scanf("%d%d", &m, &n);
    memset(lnk, -1, sizeof lnk);
    s = 0; t = n + m + 1; int sum = 0;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d", &v[i]); sum += v[i];
        memset(str, 0, sizeof str);
        cin.getline(str, 10000);
        int ulen = 0, ti;
        while(sscanf(str + ulen, "%d", &ti) == 1)
        {
            ndd[i].push_back(ti);
            if(ti == 0) ulen++;
            else
            {
                while(ti)
                    ti /= 10, ulen++;
            }
            ulen++;
        }
    }
    for(int i = 1; i <= n; ++i) scanf("%d", &tc[i]);
    for(int i = 1; i <= m; ++i) 
    {
        add(s, i, v[i]);
        for(auto p : ndd[i])
            add(i, p + m, inf_);
    }
    for(int i = 1; i <= n; ++i) add(i + m, t, tc[i]);
    int ans = sum - dinic();
    for(int i = 1; i <= m; ++i) if(level[i]) printf("%d ", i);
    putchar('\n');
    for(int i = 1; i <= n; ++i) if(level[i + m]) printf("%d ", i);
    putchar('\n');
    printf("%d\n", ans);
    return 0;
}

LOJ 6002, 最小路径覆盖

拆点, 变二分图, 对于边$(x, y)$, 连$(x, y’)$.

想想为什么是对的?

我们将点 $i$ 视为一条路径, 则二分图初始状态是每个点为一条路径, 而匹配相当于将两条路径合并. 由于匹配的定义, 每个点不能在多条路径中, 所以合法. 最大匹配数是合并的次数, 那么原图点数 - 新图最大匹配数就是答案了.

输出方案? 去**的.

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <bitset>
#include <vector>

using std::min;
using std::max;
using std::swap;
using std::bitset;
using std::vector;
using std::memset;
using std::queue;

const int maxn = 320;
const int maxm = 6005;
const int INF_ = 214748000;

struct edge
{
    int to, nxt, v;
}e[maxm << 2];
int ptr, lnk[maxn], n, m, level[maxn], s, t;
int pre[maxn], tto[maxn];
bitset<maxn> vis, out;
vector<int> vec;

inline void add(int bgn, int end, int val)
{
    e[ptr].to = end; e[ptr].v = val; e[ptr].nxt = lnk[bgn]; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].v = 0; e[ptr].nxt = lnk[end]; lnk[end] = ptr; ptr++;
}
bool bfs()
{
    memset(level, 0, sizeof level);
    queue<int> q;
    q.push(s); level[s] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].v > 0 && !level[y])
            {
                q.push(y);
                level[y] = level[u] + 1;
            }
        }
    }
    return level[t] != 0;
}
int dfs(int x, int fl)
{
    if(x == t) return fl;
    for(int p = lnk[x]; ~p; p = e[p].nxt)
    {
        int y = e[p].to;
        if(level[y] == level[x] + 1 && e[p].v != 0)
        {
            int delta = dfs(y, min(e[p].v, fl));
            if(delta > 0)
            {
                e[p].v -= delta;
                e[p ^ 1].v += delta;
                tto[x] = y;
                if(x != s) pre[y-n] = 1;
                return delta;
            }
        }
    }
    return 0;
}
int dinic()
{
    int ret = 0;
    while(bfs())
    {
        //puts("di");

        while(int delta = dfs(s, INF_))
            ret += delta;
    }
    for(int i = 1; i <= n; ++i)
    {
        if(!pre[i])
        {
            int cur = i;
            printf("%d ", cur);
            while(tto[cur] && tto[cur] != t)
            {
                printf("%d ", tto[cur] - n);
                cur = tto[cur] - n;
            }
            putchar('\n');
        }
    }
    return ret;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(lnk, -1, sizeof lnk);
    s = 0; t = 2 * n + 1;
    int x, y;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &x, &y);
        add(x, y + n, 1);
    }
    for(int i = 1; i <= n; ++i)
        add(s, i, 1), add(i + n, t, 1);
    int ans = n - dinic();
    printf("%d\n", ans);
    return 0;
}

LOJ 6003, 最大流

预处理完全平方数, 每次加入一个球, 枚举前面的球, 如果有能构成完全平方数的就连边. 从源点连向新加入点, 代表开启一个柱子, 拆点, 代表次数限制.

输出方案? ****.

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <queue>

using std::min;
using std::max;
using std::memset;
using std::swap;
using std::bitset;
using std::queue;

const int maxn = 65;
const int INF_ = 0x3f3f3f3f;

struct edge
{
    int to, nxt, v;
}e[100005];
int lnk[maxn + 10000], ptr, n, mtc[maxn + 10000], s, t;
int level[maxn + 10000];
int now = 1, res = 1;
bitset<maxn + 10000> tag;
bitset<5001> sqr;

void add(int bgn, int end, int val)
{
    e[ptr].to = end; e[ptr].v = val; e[ptr].nxt = lnk[bgn]; lnk[bgn] = ptr; ++ptr;
    e[ptr].to = bgn; e[ptr].v = 0; e[ptr].nxt = lnk[end]; lnk[end] = ptr; ++ptr;
}
bool bfs()
{
    queue<int> q;
    memset(level,0,sizeof(level));
    level[s] = 1; 
    q.push(s);
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int p = lnk[u]; p != -1; p = e[p].nxt){
            int y = e[p].to;
            if(e[p].v > 0 && !level[y]){
                level[y] = level[u] + 1;
                q.push(y);
            }
        }
    }
    if(level[t] == 0) return false;
    else return true;
}
int dfs(int x, int fl)
{
    if(x == t)return fl;
    for(int p = lnk[x]; p != -1; p = e[p].nxt){
        int y = e[p].to;
        if(level[y] == level[x] + 1 && e[p].v != 0) {
            int delta = dfs(y, min(fl, e[p].v));
            if(delta > 0) {
                e[p].v -= delta;
                e[p^1].v += delta;
                return delta;
            }
        }   
    }
    //cerr<<"dfs end"<<endl;
    return 0;
}
void dinic()
{
    while(bfs()) {
        //puts("dinic");
        while(int delta = dfs(s, INF_))
            res -= delta;
    }
}

int main()
{
    memset(lnk, -1, sizeof(lnk));
    scanf("%d", &n);
    s = 0; t = 10005;
    for(int i = 1; i * i <= 5000; ++i) sqr.set(i * i);
    while(1)
    {
        add(s, now, 1); add(now + 5000, t, 1);
        for(int i = 1; i < now; ++i)
            if(sqr.test(i + now)) add(i, now + 5000, 1);
        dinic();
        if(res > n) break;
        now++; res++;
    }
    printf("%d\n", now - 1);
    for(int i = 1; i < now; ++i)
    {
        for(int p = lnk[i]; ~p; p = e[p].nxt)
        {
            if(!e[p].v) {mtc[i] = e[p].to - 5000; break;}
        }
    }
    for(int i = 1; i < now; ++i)
    {
        if(tag.test(i)) continue; int tmp = i;
        while(tmp != -5000)
        {
            tag.set(tmp);
            printf("%d ", tmp);
            tmp = mtc[tmp];
        }
        putchar('\n');
    }
    return 0;
}

LOJ 6004, 最大流.

源点到国家, 国家到每个桌子, 桌子到汇点.

源点出边满流则合法.

输出方案?

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;

const int maxn = 500;
const int inf_ = 0x3f3f3f3f;
const int maxe = 2e+5 + 5;

struct edge
{
    int to, nxt, v;
}e[maxe];
int ptr, lnk[maxn], level[maxn];
int cur[maxn];
int n, m, s, t;
queue<int> q;

inline void add(int bgn, int end, int val)
{
    e[ptr].to = end; e[ptr].nxt = lnk[bgn]; e[ptr].v = val; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].nxt = lnk[end]; e[ptr].v = 0; lnk[end] = ptr; ptr++;
}
inline bool bfs()
{
    memset(level, 0, sizeof level);
    q.push(s); level[s] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].v > 0 && !level[y])
            {
                level[y] = level[u] + 1;
                q.push(y);
            }
        }
    }
    return level[t] != 0;
}
int dfs(int x, int fl)
{
    if(x == t) return fl;
    for(int &p = cur[x]; ~p; p = e[p].nxt)
    {
        int y = e[p].to;
        if(e[p].v && level[y] == level[x] + 1)
        {
            int delta = dfs(y, min(fl, e[p].v));
            if(delta > 0)
            {
                e[p].v -= delta;
                e[p^1].v += delta;
                return delta;
            }
        }
    }
    return 0;
}
int dinic()
{
    int ret = 0;
    while(bfs())
    {
        memcpy(cur, lnk, sizeof lnk);
        while(int delta = dfs(s, inf_))
            ret += delta;
    }
    return ret;
}

int main()
{
    scanf("%d%d", &m, &n);
    memset(lnk, -1, sizeof lnk);
    s = 0; t = n + m + 1; int sum = 0;
    int c;
    for(int i = 1; i <= m; ++i)
        scanf("%d", &c), add(s, i, c), sum += c;
    for(int i = 1; i <= n; ++i)
        scanf("%d", &c), add(i + m, t, c);
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            add(i, j + m, 1);
    int ret = dinic();
    //printf("%d\n", ret); 
    if(ret != sum) {puts("0"); return 0;}
    puts("1");
    for(int i = 1; i <= m; ++i)
    {
        for(int p = lnk[i]; ~p; p = e[p].nxt)
        {
            if(e[p].to != s && e[p].v == 0)
                printf("%d ", e[p].to - m);
        }
        putchar('\n');
    }
    return 0;
}

LOJ 6005, 最大流

第一问DP, 没什么好说的.

第二问, 从 $S$ 开始, 依次按 $f[i]$ 严格递增1, $a[i]$ 递增连边, 直到 $T$. 记得拆点表示次数限制. 这样最大流就是答案.

第三问, 拆点时的次数限制和源汇对于1, n的次数限制修改一下.

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include<queue>

using namespace std;

const int maxn = 505;
const int inf_ = 0x3f3f3f3f;

struct edge
{
    int to, nxt, v;
}e[maxn * maxn << 1];
int n, a[maxn], s, t;
int f[maxn];
int ptr, lnk[maxn << 1], level[maxn << 1];
queue<int> q;

inline void add(int bgn, int end, int val)
{
    e[ptr].to = end; e[ptr].nxt = lnk[bgn]; e[ptr].v = val; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].nxt = lnk[end]; e[ptr].v = 0; lnk[end] = ptr; ptr++;
}
inline bool bfs()
{
    memset(level, 0, sizeof level);
    q.push(s); level[s] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].v && !level[y])
            {
                level[y] = level[u] + 1;
                q.push(y);
            }
        }
    }
    return level[t] != 0;
}
int dfs(int x, int fl)
{
    if(x == t) return fl;
    for(int p = lnk[x]; ~p; p = e[p].nxt)
    {
        int y = e[p].to;
        if(e[p].v && level[y] == level[x] + 1)
        {
            int delta = dfs(y, min(fl, e[p].v));
            if(delta > 0)
            {
                e[p].v -= delta;
                e[p^1].v += delta;
                return delta;
            }
        }
    }
    return 0;
}
int dinic()
{
    int ret = 0;
    while(bfs())
    {
        while(int delta = dfs(s, inf_))
            ret += delta;
    }
    return ret;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    memset(lnk, -1, sizeof lnk);
    int ans = 0;
    for(int i = 1; i <= n; ++i)
    {
        f[i] = 1;
        for(int j = 1; j < i; ++j)
            if(a[j] <= a[i]) f[i] = max(f[j] + 1, f[i]);
        ans = max(ans, f[i]);
    }
    printf("%d\n", ans);
    s = 0; t = n * 2 + 1;
    for(int i = 1; i <= n; ++i)
    {
        add(i, i + n, 1);
        if(f[i] == 1) add(s, i, 1);
        if(f[i] == ans) add(i + n, t, 1);
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j < i; ++j)
            if(f[j] + 1 == f[i] && a[j] <= a[i])
                add(j + n, i, 1);
    int ret = dinic();
    printf("%d\n", ret);
    memset(lnk, -1, sizeof lnk); ptr = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(i == 1 || i == n) add(i, i + n, inf_);
        else add(i, i + n, 1);
        if(f[i] == 1) add(s, i, (i==1)?inf_:1);
        if(f[i] == ans) add(i + n, t, (i==n)?inf_:1);
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j < i; ++j)
            if(f[j] + 1 == f[i] && a[j] <= a[i])
                add(j + n, i, 1);
    ret = dinic();
    printf("%d\n", ret);    
    return 0;
}

LOJ 6006, 最大流

源点连题, 题连类型, 类型连汇. 满流即合法.

输出方案?

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <queue>
#include <vector>

using namespace std;

const int maxn = 2005;
const int inf = 0x3f3f3f3f;

struct edge
{
    int to, nxt, v;
}e[maxn << 2];
int ptr, lnk[maxn], n, k, level[maxn];
int s, t;
queue<int> q;
vector<int> pre[maxn];

inline void add(int bgn, int end, int val)
{
    e[ptr].to = end; e[ptr].nxt = lnk[bgn]; e[ptr].v = val; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].nxt = lnk[end]; e[ptr].v = 0; lnk[end] = ptr; ptr++;
}
inline bool bfs()
{
    memset(level, 0, sizeof level);
    q.push(s); level[s] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].v > 0 && !level[y])
            {
                level[y] = level[u] + 1;
                q.push(y);
            }
        }
    }
    return level[t] != 0;
}
int dfs(int x, int fl)
{
    if(x == t) return fl;
    for(int p = lnk[x]; ~p; p = e[p].nxt)
    {
        int y = e[p].to;
        if(level[y] == level[x] + 1 && e[p].v)
        {
            int delta = dfs(y, min(fl, e[p].v));
            if(delta > 0)
            {
                if(x != s && y != t)
                    pre[y-n].push_back(x);
                e[p].v -= delta;
                e[p ^ 1].v += delta;
                return delta;
            }
        }
    }
    return 0;
}
int dinic()
{
    int ret = 0;
    while(bfs())
    {
        while(int delta = dfs(s, inf))
            ret += delta;
    }
    return ret;
}
                            

int main()
{
    int m = 0;
    scanf("%d%d", &k, &n);
    memset(lnk, -1, sizeof lnk);
    s = 0; t = n + k + 1;
    for(int i = 1; i <= k; ++i)
    {
        int ndd; scanf("%d", &ndd);
        m += ndd;
        add(i + n, t, ndd);
    }
    for(int i = 1; i <= n; ++i)
    {
        add(s, i, 1);
        int p, tp;
        scanf("%d", &p);
        for(int j = 1; j <= p; ++j)
        {
            scanf("%d", &tp);
            add(i, tp + n, 1);
        }
    }
    int ret = dinic();
    if(ret != m)
    {
        puts("No Solution!");
        return 0;
    }    
    for(int i = 1; i <= k; ++i)
    {
        printf("%d: ", i);
        for(auto v : pre[i])
            printf("%d ", v);
        putchar('\n');
    }
    return 0;
}

LOJ 6007,最小割

奇偶建图, 相邻则分属不同集合, 中间连$\infty$, 这样想割掉就一定分属于不同集合.

最后总和减去最小割.

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using std::min;
using std::max;
using std::swap;
using std::memset;
using std::queue;
using std::cerr;
using std::endl;

const int maxn = 105;
constexpr int maxp = maxn * maxn;
const int INF_ = 0x3f3f3f3f;

struct edge
{
    int to, nxt, v;
}e[maxp << 2];
int n, m, lnk[maxp], ptr, mtr[maxn][maxn];
int level[maxp];
int s, t;

void add(int bgn, int end, int val)
{
    e[ptr].to = end; e[ptr].v = val; e[ptr].nxt = lnk[bgn]; lnk[bgn] = ptr; ++ptr;
    e[ptr].to = bgn; e[ptr].v = 0; e[ptr].nxt = lnk[end]; lnk[end] = ptr; ++ptr;
}
bool bfs()
{
    //cerr << "bfs begin" << endl;
    queue<int> q;
    memset(level, 0, sizeof(level));
    level[s] = 1; 
    q.push(s);
    while(!q.empty()){
        int u = q.front();q.pop();
        for(int p = lnk[u]; p != -1; p = e[p].nxt){
            int y = e[p].to;
            if(e[p].v > 0 && !level[y]){
                level[y] = level[u] + 1;
                q.push(y);
            }
        }
    }
    //cerr << "bfs end" << endl;
    if(level[t] == 0) return false;
    else return true;
}
int dfs(int x, int fl)
{
    if(x == t) return fl;
    for(int p = lnk[x]; ~p; p = e[p].nxt){
        int y = e[p].to;
        if(level[y] == level[x] + 1 && e[p].v != 0) {
            int delta = dfs(y, min(fl, e[p].v));
            if(delta > 0) {
                e[p].v -= delta;
                e[p^1].v += delta;
                return delta;
            }
        }   
    }
    return 0;
}
int dinic()
{
    int ret = 0;
    while(bfs()) {
    	//cerr << "dfs" << endl;
        while(int delta = dfs(s, INF_))
            ret += delta;
    }
    return ret;
}

inline bool ok(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m;
}
inline int id(int x, int y)
{
    return (x - 1) * m + y;
}

int main()
{
    memset(lnk, -1, sizeof lnk);
    int sum = 0, res = 0;
    scanf("%d%d", &n, &m);
    s = 0; t = n * m + 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            scanf("%d", &mtr[i][j]);
            sum += mtr[i][j];
            if((i + j) & 1)
            {
                add(s, (i - 1) * m + j, mtr[i][j]);
                if(ok(i - 1, j)) add(id(i, j), id(i - 1, j), INF_);
                if(ok(i + 1, j)) add(id(i, j), id(i + 1, j), INF_);
                if(ok(i, j + 1)) add(id(i, j), id(i, j + 1), INF_);
                if(ok(i, j - 1)) add(id(i, j), id(i, j - 1), INF_);
            }
            else
            {
                add((i - 1) * m + j, t, mtr[i][j]);
            }
        }
    res = dinic();
    printf("%d\n", sum - res);
    return 0;
}

LOJ 6008, 费用流

源向每天连$\infty$, 费用 $P$. 想买多少买多少(哼).

每天向汇连需求, 表示使用的餐巾.

每天拆点向外连洗餐巾的边, 向下一天连延迟的边.

源点向每天拆点连每天需求的边, 表示每天产生的脏餐巾.

求最小费用.

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using std::min;
using std::max;
using std::swap;
using std::memset;
using std::queue;

typedef long long ll;

const ll maxn = 4505;
const ll maxm = 50005;
const ll inf_ = 0x3f3f3f3f;

struct edge
{
    ll to,nxt,w,c;
}e[maxm << 1];
struct node
{
    ll fl,ct;
    node(ll f = inf_,ll c = 0)
    {
        fl = f;
        ct = c;
    }
};
ll n,m,s,t,lnk[maxn],ptr,dis[maxn],vis[maxn];
ll pre[maxn],id[maxn],r[maxn];
queue<ll> q;

void add(ll bgn,ll end,ll val,ll cos)
{
    e[ptr].to = end; e[ptr].w = val; e[ptr].nxt = lnk[bgn]; lnk[bgn] = ptr; e[ptr].c = cos; ptr++;
    e[ptr].to = bgn; e[ptr].w = 0;  e[ptr].nxt = lnk[end]; lnk[end] = ptr; e[ptr].c = -cos; ptr++;
}
bool spfa(ll S,ll T)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    q.push(S), vis[S] = 1, dis[S] = 0;
    while(!q.empty())
    {
        ll u = q.front(); q.pop(); vis[u] = 0;
        for(ll p = lnk[u]; ~p; p = e[p].nxt)
        {
            ll y = e[p].to;
            if(e[p].w > 0 && dis[u] + e[p].c < dis[y])
            {
                dis[y] = dis[u] + e[p].c;
                pre[y] = u;
                id[y] = p;
                if(!vis[y])vis[y] = 1,q.push(y);
            }
        }
    }
    return dis[T] < inf_;
}
node dfs(ll S,ll T)
{
    ll flow = 0,cost = 0,aug;
    while(spfa(S,T))
    {
        aug = inf_;
        for(ll p = T; p != S; p = pre[p])
            aug = min(aug, e[id[p]].w);
        cost += aug * dis[T];
        flow += aug;
        for(ll p = T; p != S; p = pre[p])
            e[id[p]].w -= aug, e[id[p]^1].w += aug;
    }
    return node(flow,cost);
}

signed main()
{
    ll N, M, P, S, F;
    memset(lnk,-1,sizeof(lnk));
    scanf("%lld", &n);
    for(ll i = 1; i <= n; ++i) scanf("%lld", &r[i]);
    scanf("%lld%lld%lld%lld%lld", &P, &M, &F, &N, &S);
    s = 0; t = (n << 1) + 1;
    for(ll i = 1; i <= n; ++i)
        add(s, i, inf_, P), add(i, t, r[i], 0);
    for(ll i = n + 1; i < t; ++i)
    {
        if(i - n + M <= n) add(i, i - n + M, inf_, F);
        if(i - n + N <= n) add(i, i - n + N, inf_, S);
        if(i < t - 1) add(i, i + 1, inf_, 0);
        add(s, i, r[i - n], 0);
    }
    node res = dfs(s,t);
    printf("%lld\n", res.ct);
    return 0;
}

LOJ 6009, 状态压缩

状压SPFA啦.

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using std::min;
using std::max;
using std::memset;
using std::queue;
using std::swap;

const int maxn = 23;
const int maxm = 105;
constexpr int maxs = 1 << maxn;
const int INF_ = 2147480000;

int dpn[maxm], ecp[maxm], fix[maxm], led[maxm], t[maxm];
int n, m;
char prp1[maxn], prp2[maxn];
int dis[maxs], vis[maxs], lim;
queue<int> q;

void spfa()
{
    for(int i = 0; i <= (1 << n); ++i) dis[i] = INF_;
    dis[lim] = 0;
    q.push(lim); vis[lim] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        vis[u] = 0;
        for(int p = 1; p <= m; ++p)
        {
            if((ecp[p] & (~u)) == ecp[p] && (dpn[p] & u) == dpn[p])
            {
                int y = u & (~fix[p]) | led[p];
                if(dis[y] > dis[u] + t[p])
                {
                    dis[y] = dis[u] + t[p];
                    if(!vis[y])
                    {
                        q.push(y);
                        vis[y] = 1;
                    }
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    lim = (1 << n) - 1;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%s%s", &t[i], prp1, prp2);
        for(int j = 0; j < n; ++j)
        {
            if(prp1[j] == '+') dpn[i] |= (1 << j);
            else if(prp1[j] == '-') ecp[i] |= (1 << j);
            if(prp2[j] == '-') fix[i] |= (1 << j);
            else if(prp2[j] == '+') led[i] |= (1 << j);
        }
    }
    spfa();
    if(dis[0] == INF_) puts("0");
    else printf("%d\n", dis[0]);
    return 0;
}

LOJ 6010, 费用流

次数限制搞一搞, 熟悉的拆点套路.

点限制就在拆点里搞, 边限制就在转移上搞, 也就是1或者$\infty$.

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <bitset>

using namespace std;

const int maxn = 100;
const int maxp = 5005;
const int inf_ = 0x3f3f3f3f;

struct edge
{
    int to, nxt, w, c;
    constexpr edge(int t_ = 0, int x_ = 0, int w_ = 0, int c_ = 0):
    to(t_), nxt(x_), w(w_), c(c_) {}
}e[50005];
int n, m, s, t, mtr[maxn][maxn], amap[maxp], mp[maxn][maxn];
int id[maxp], pre[maxp], dis[maxp], num, ptr, lnk[maxp];
bitset<maxp> vis;
queue<int> q;

inline void add(int bgn, int end, int val, int cost)
{
    e[ptr] = edge(end, lnk[bgn], val, cost); lnk[bgn] = ptr; ptr++;
    e[ptr] = edge(bgn, lnk[end], 0, -cost); lnk[end] = ptr; ptr++; 
}
inline bool spfa(int S, int T)
{
    for(int i = S; i <= T; ++i) dis[i] = inf_;
    vis.reset(); q.push(S); vis[S] = 1; dis[S] = 0;
    while(!q.empty())
    {
        int u = q.front(); q.pop(); vis[u] = 0;
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].w && dis[y] > dis[u] + e[p].c)
            {
                dis[y] = dis[u] + e[p].c;
                pre[y] = u; id[y] = p;
                if(!vis[y]) vis[y] = 1, q.push(y);
            }
        }
    }
    return dis[T] < inf_;
}
inline int cost_flow(int S, int T)
{
    int cost = 0, flow = 0, aug;
    while(spfa(S, T))
    {
        aug = inf_;
        for(int p = T; p != S; p = pre[p])
            aug = min(aug, e[id[p]].w);
        flow += aug;
        cost += aug * dis[T];
        for(int p = T; p != S; p = pre[p])
            e[id[p]].w -= aug, e[id[p]^1].w += aug;
    }
    return cost;
}

int main()
{
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j < m + i; ++j)
            scanf("%d", &mtr[i][j]), 
            mp[i][j] = ++num, 
            amap[num] = mtr[i][j];
    }
    s = 0; t = num * 2 + 1;
    //-------1-----------
    memset(lnk, -1, sizeof lnk); ptr = 0;
    for(int i = 1; i <= m; ++i)
        add(s, mp[1][i], 1, 0);
    for(int i = 1; i <= num; ++i)
        add(i, i + num, 1, -amap[i]);
    for(int i = 1; i < n + m; ++i)
        add(mp[n][i] + num, t, 1, 0);
    for(int i = 1; i < n; ++i)
    {
        for(int j = 1; j < m + i; ++j)
            add(mp[i][j] + num, mp[i+1][j], 1, 0),
            add(mp[i][j] + num, mp[i+1][j+1], 1, 0);
    }
    int ret = cost_flow(s, t);
    printf("%d\n", -ret);
    //-------2-----------
    memset(lnk, -1, sizeof lnk); ptr = 0;
    for(int i = 1; i <= m; ++i)
        add(s, mp[1][i], 1, 0);
    for(int i = 1; i <= num; ++i)
        add(i, i + num, inf_, -amap[i]);
    for(int i = 1; i < n + m; ++i)
        add(mp[n][i] + num, t, inf_, 0);
    for(int i = 1; i < n; ++i)
    {
        for(int j = 1; j < m + i; ++j)
            add(mp[i][j] + num, mp[i+1][j], 1, 0),
            add(mp[i][j] + num, mp[i+1][j+1], 1, 0);
    }
    ret = cost_flow(s, t);
    printf("%d\n", -ret);
    //-------3-----------
    memset(lnk, -1, sizeof lnk); ptr = 0;
    for(int i = 1; i <= m; ++i)
        add(s, mp[1][i], 1, 0);
    for(int i = 1; i <= num; ++i)
        add(i, i + num, inf_, -amap[i]);
    for(int i = 1; i < n + m; ++i)
        add(mp[n][i] + num, t, inf_, 0);
    for(int i = 1; i < n; ++i)
    {
        for(int j = 1; j < m + i; ++j)
            add(mp[i][j] + num, mp[i+1][j], inf_, 0),
            add(mp[i][j] + num, mp[i+1][j+1], inf_, 0);
    }
    ret = cost_flow(s, t);
    printf("%d\n", -ret);
    return 0;
}

LOJ 6011, 费用流

啊, 看着办.

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<queue>

using namespace std;

const int maxn = 205;
const int inf_ = 0x3f3f3f3f;

struct edge
{
    int to, nxt, w, c;
}e[maxn * maxn];
int n, m, lnk[maxn], level[maxn], dis[maxn], pre[maxn];
int id[maxn], a[maxn], b[maxn], s, t;
int c[maxn][maxn];
int ptr;
bitset<maxn> vis;
queue<int> q;

inline void add(int bgn, int end, int val, int cost)
{
    e[ptr].to = end; e[ptr].nxt = lnk[bgn]; 
    e[ptr].w = val; e[ptr].c = cost; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].nxt = lnk[end];
    e[ptr].w = 0; e[ptr].c = -cost; lnk[end] = ptr; ptr++;
}
inline bool spfa(int S, int T)
{
    for(int i = S; i <= T; ++i) dis[i] = 0x3f3f3f3f;
    //memset(vis, 0, sizeof vis);
    vis.reset();
    q.push(S); vis[S] = 1; dis[S] = 0;
    while(!q.empty())
    {
        int u = q.front(); q.pop(); vis[u] = 0;
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].w > 0 && dis[u] + e[p].c < dis[y])
            {
                dis[y] = dis[u] + e[p].c;
                pre[y] = u;
                id[y] = p;
                if(!vis[y]) vis[y] = 1, q.push(y);
            }
        }
    }
    return dis[T] < inf_;
}
int dfs(int S, int T)
{
    int flow = 0, cost = 0, aug;
    while(spfa(S, T))
    {
        aug = inf_;
        for(int p = T; p != S; p = pre[p])
            aug = min(aug, e[id[p]].w);
        cost += aug * dis[T];
        flow += aug;
        for(int p = T; p != S; p = pre[p])
            e[id[p]].w -= aug, e[id[p]^1].w += aug;
    }
    return cost;
}


int main()
{
    memset(lnk, -1, sizeof lnk);
    scanf("%d%d", &m, &n);
    s = 0; t = n + m + 1;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d", &a[i]);
        add(s, i, a[i], 0);
    }
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &b[i]);
        add(i + m, t, b[i], 0);
    }
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
        {
            scanf("%d", &c[i][j]);
            add(i, j + m, 0x3f3f3f3f, c[i][j]);
        }
    printf("%d\n", dfs(s, t));
    //-----------------------------
    memset(lnk, -1, sizeof lnk);
    for(int i = 1; i <= m; ++i)
        add(s, i, a[i], 0);
    for(int i = 1; i <= n; ++i)
        add(i + m, t, b[i], 0);
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j)
            add(i, j + m, 0x3f3f3f3f, -c[i][j]);
    int ret = -dfs(s, t);
    printf("%d\n", ret);
    return 0;
}

LOJ 6012, 费用流

啊, 看着办.

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <bitset>

using namespace std;

const int maxn = 205;
const int inf_ = 0x3f3f3f3f;

struct edge
{
    int to, nxt, w, c;
}e[maxn * maxn << 2];
int n, s, t, lnk[maxn], ptr, pre[maxn], id[maxn];
int dis[maxn];
int c[maxn][maxn];
queue<int> q;
bitset<maxn> vis;

inline void add(int bgn, int end, int val, int cost)
{
    e[ptr].to = end; e[ptr].w = val; e[ptr].c = cost; 
    e[ptr].nxt = lnk[bgn]; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].w = 0; e[ptr].c = -cost;
    e[ptr].nxt = lnk[end]; lnk[end] = ptr; ptr++;
}
bool spfa(int S, int T)
{
    for(int i = S; i <= T; ++i) dis[i] = inf_;
    vis.reset();
    q.push(S), vis[S] = 1; dis[S] = 0;
    while(!q.empty())
    {
        int u = q.front(); q.pop(); vis[u] = 0;
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].w > 0 && dis[u] + e[p].c < dis[y])
            {
                dis[y] = dis[u] + e[p].c;
                pre[y] = u;
                id[y] = p;
                if(!vis[y]) vis[y] = 1, q.push(y);
            }
        }
    }
    return dis[T] < inf_;
}
int cost_flow(int S, int T)
{
    int flow = 0, cost = 0, aug;
    while(spfa(S, T))
    {
        aug = inf_;
        for(int p = T; p != S; p = pre[p])
            aug = min(aug, e[id[p]].w);
        cost += aug * dis[T];
        flow += aug;
        for(int p = T; p != S; p = pre[p])
            e[id[p]].w -= aug, e[id[p]^1].w += aug;
    }
    return cost;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            scanf("%d", &c[i][j]);
    s = 0; t = n * 2 + 1;
    memset(lnk, -1, sizeof lnk);
    for(int i = 1; i <= n; ++i)
        add(s, i, 1, 0), add(i + n, t, 1, 0);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            add(i, j + n, inf_, c[i][j]);
    int ret = cost_flow(s,t);
    printf("%d\n", ret);
    memset(lnk, -1, sizeof lnk);
    ptr = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            add(i, j + n, inf_, -c[i][j]);
    for(int i = 1; i <= n; ++i)
        add(s, i, 1, 0), add(i + n, t, 1, 0);
    ret = cost_flow(s, t);
    printf("%d\n", -ret);
    return 0;
}

LOJ 6013, 费用流

最后肯定是到平均值, 所以缺的就从源点来, 多的就从汇点走, 然后拆点, 出点向相邻的入点连费用为1的边, 也就是搬运.

最小费用就好.

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <bitset>

using namespace std;

const int maxn = 205;
const int inf_ = 0x3f3f3f3f;

struct edge
{
    int to, nxt, w, c;
}e[maxn * maxn << 2];
int n, s, t, lnk[maxn], ptr, pre[maxn], id[maxn];
int dis[maxn];
int c[maxn][maxn];
queue<int> q;
bitset<maxn> vis;

inline void add(int bgn, int end, int val, int cost)
{
    e[ptr].to = end; e[ptr].w = val; e[ptr].c = cost; 
    e[ptr].nxt = lnk[bgn]; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].w = 0; e[ptr].c = -cost;
    e[ptr].nxt = lnk[end]; lnk[end] = ptr; ptr++;
}
bool spfa(int S, int T)
{
    for(int i = S; i <= T; ++i) dis[i] = inf_;
    vis.reset();
    q.push(S), vis[S] = 1; dis[S] = 0;
    while(!q.empty())
    {
        int u = q.front(); q.pop(); vis[u] = 0;
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].w > 0 && dis[u] + e[p].c < dis[y])
            {
                dis[y] = dis[u] + e[p].c;
                pre[y] = u;
                id[y] = p;
                if(!vis[y]) vis[y] = 1, q.push(y);
            }
        }
    }
    return dis[T] < inf_;
}
int cost_flow(int S, int T)
{
    int flow = 0, cost = 0, aug;
    while(spfa(S, T))
    {
        aug = inf_;
        for(int p = T; p != S; p = pre[p])
            aug = min(aug, e[id[p]].w);
        cost += aug * dis[T];
        flow += aug;
        for(int p = T; p != S; p = pre[p])
            e[id[p]].w -= aug, e[id[p]^1].w += aug;
    }
    return cost;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            scanf("%d", &c[i][j]);
    s = 0; t = n * 2 + 1;
    memset(lnk, -1, sizeof lnk);
    for(int i = 1; i <= n; ++i)
        add(s, i, 1, 0), add(i + n, t, 1, 0);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            add(i, j + n, inf_, c[i][j]);
    int ret = cost_flow(s,t);
    printf("%d\n", ret);
    memset(lnk, -1, sizeof lnk);
    ptr = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            add(i, j + n, inf_, -c[i][j]);
    for(int i = 1; i <= n; ++i)
        add(s, i, 1, 0), add(i + n, t, 1, 0);
    ret = cost_flow(s, t);
    printf("%d\n", -ret);
    return 0;
}

顺便说一句, 这题也能上树, 一样的, 也能带权, 一样的.

LOJ 6014, 费用流

这题神.

从源点开始, 一路向前连流量 $k$, 费用 $0$ 的边. 这样就是流入的流量只能供上 $k$ 条线段. 而且从线段流走了以后, 在她流回来之前都不能再多了. 所以线段把左右端点连起来, 只有一次, 费用 $len[i]$.

最大费用就行了.

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <queue>

using namespace std;

const int maxn = 1005;
const int inf_ = 0x3f3f3f3f;

struct edge
{
    int to, nxt, w, c;
}e[maxn << 2];
int n, k, s, t;
int l[maxn], r[maxn], cpy[maxn], len, tot;
int wid[maxn], ptr;
int pre[maxn], id[maxn], dis[maxn], vis[maxn], lnk[maxn];
queue<int> q;

inline void add(int bgn, int end, int val, int cost)
{
    e[ptr].to = end; e[ptr].w = val; e[ptr].c = cost;
    e[ptr].nxt = lnk[bgn]; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].w = 0; e[ptr].c = -cost;
    e[ptr].nxt = lnk[end]; lnk[end] = ptr; ptr++;
}
inline bool spfa(int S, int T)
{
    for(int i = S; i <= T; ++i) dis[i] = inf_;
    q.push(S); dis[S] = 0; vis[S] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop(); vis[u] = 0;
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].w && dis[y] > dis[u] + e[p].c)
            {
                dis[y] = dis[u] + e[p].c; pre[y] = u; id[y] = p;
                if(!vis[y])
                    vis[y] = 1, q.push(y);
            }
        }
    }
    return dis[T] < inf_;
}
inline int cost_flow(int S, int T)
{
    int cost = 0, flow = 0, aug;
    while(spfa(s, t))
    {
        aug = inf_;
        for(int p = T; p != S; p = pre[p])
            aug = min(aug, e[id[p]].w);
        cost += aug * dis[T];
        flow += aug;
        for(int p = T; p != S; p = pre[p])
            e[id[p]].w -= aug, e[id[p]^1].w += aug;
    }
    return cost;
}

int main()
{
    scanf("%d%d", &n, &k);
    memset(lnk, -1, sizeof lnk);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &l[i], &r[i]); 
        if(l[i] > r[i]) swap(l[i], r[i]);
        wid[i] = r[i] - l[i];
        cpy[++tot] = l[i]; cpy[++tot] = r[i];
    }
    sort(cpy + 1, cpy + 1 + tot);
    int len = unique(cpy, cpy + 1 + tot) - (cpy + 1);
    for(int i = 1; i <= n; ++i)
        l[i] = lower_bound(cpy + 1, cpy + 1 + len, l[i]) - cpy,
        r[i] = lower_bound(cpy + 1, cpy + 1 + len, r[i]) - cpy;
    s = 0; t = len + 1;
    for(int i = 1; i <= len + 1; ++i)
        add(i - 1, i, k, 0);
    for(int i = 1; i <= n; ++i)
        add(l[i], r[i], 1, -wid[i]);
    int ret = cost_flow(s, t);
    printf("%d\n", -ret);
    return 0;
}

LOJ 6015, 最大流

不好求, 改验证, 每次加入一天, 就从最后一天流向新的一天, 同时源点向新的地球送 $\infty$.

直到最大流满足要求.

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int maxn = 100;
const int inf_ = 0x3f3f3f3f;

int n, m, k, h[maxn], r[maxn];
int f[maxn];
vector<int> rtn[maxn];

int find(int x)
{
    return (f[x] == x) ? x : f[x] = find(f[x]);
}
void link(int x, int y)
{
    int fx = find(x), fy = find(y);
    if(fx != fy) f[fx] = fy;
}

struct edge
{
    int to, nxt, v;
}e[500005];
int ptr, lnk[500005], s, t, level[500005], cur[500005];
queue<int> q;

inline void add(int bgn, int end, int val)
{
    e[ptr].to = end; e[ptr].nxt = lnk[bgn]; e[ptr].v = val; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].nxt = lnk[end]; e[ptr].v = 0; lnk[end] = ptr; ptr++;
}
inline bool bfs()
{
    memset(level, 0, sizeof level);
    q.push(s); level[s] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].v > 0 && !level[y])
            {
                level[y] = level[u] + 1;
                q.push(y);
            }
        }
    }
    return level[t] != 0;
}
int dfs(int x, int fl)
{
    if(x == t) return fl;
    for(int &p = cur[x]; ~p; p = e[p].nxt)
    {
        int y = e[p].to;
        if(e[p].v && level[y] == level[x] + 1)
        {
            int delta = dfs(y, min(fl, e[p].v));
            if(delta > 0)
            {
                e[p].v -= delta;
                e[p^1].v += delta;
                return delta;
            }
        }
    }
    return 0;
}
inline int dinic()
{
    int ret = 0;
    while(bfs())
    {
        memcpy(cur, lnk, sizeof lnk);
        while(int delta = dfs(s, inf_))
            ret += delta;
    }
    return ret;
}


int main()
{
    scanf("%d%d%d", &n, &m, &k);
    memset(lnk, -1, sizeof lnk);
    for(int i = 0; i <= n + 1; ++i) f[i] = i;
    s = 0, t = 1;
    int base = 2 + n + 1, lstbase = 2;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &h[i], &r[i]);
        int x;
        for(int j = 1; j <= r[i]; ++j)
        {
            scanf("%d", &x);
            if(x == -1) x = n+1;
            rtn[i].push_back(x);
            if(j > 1) link(x, rtn[i][j - 2]);
        }
    }
    if(find(0) != find(n+1))
    {puts("0"); return 0;}
    int ret = 0;
    add(s, lstbase, inf_);
    for(int ans = 1; ; ++ans)
    {
        add(s, base, inf_);
        for(int i = 1; i <= n; ++i)
            add(lstbase + i, base + i, inf_);
        for(int i = 1; i <= m; ++i)
        {
            //if(base == 2) continue;
            int pos = ans % r[i], lst = (pos - 1 + r[i]) % r[i];
            add(rtn[i][lst] == n+1 ? t : lstbase+rtn[i][lst], rtn[i][pos] == n+1 ? t : base+rtn[i][pos] , h[i]);
        }
        ret += dinic();
        //printf("%d\n", ret);
        if(ret >= k)
        {
            printf("%d\n", ans);
            return 0;
        }
        lstbase = base;
        base += n+1;
    }
    return 0;
}

LOJ 6121, ~~状压分层图最短路

嗯嗯嗯? 

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <bitset>
#include <queue>

using namespace std;

const int maxn = 12;
const int maxp = maxn * maxn;

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

struct edge
{
    int to, nxt, tp;
    constexpr edge(int t_ = 0, int x_ = 0, int p_ = 0):
    to(t_), nxt(x_), tp(p_){}
}e[maxp << 3];
struct node
{
    int po, sta;
    constexpr node(int p_, int s_):po(p_),sta(s_){}
};
int ptr, lnk[maxp], dis[maxp][1030], key[maxp];
int n, m, p, k, s, num, id[maxn][maxn];
int flo[maxp][maxp];
int x1, yone, x2, y2, g; int px[15], py[15], ty[15];
bool vis[maxp][1030];
queue<node> q;

inline void add(int bgn, int end, int typ_)
{
    e[++ptr] = edge(end, lnk[bgn], typ_); lnk[bgn] = ptr;
}
inline void bfs()
{
    for(int i = 0; i <= num; ++i)
        for(int j = 0; j <= (1 << s) - 1; ++j)
            dis[i][j] = 0x3f3f3f3f;
    q.push(node(1, key[1])); dis[1][key[1]] = 0; vis[1][key[1]] = 1;
    while(!q.empty())
    {
        node u = q.front(); q.pop();
        vis[u.po][u.sta] = 0;
        for(int p = lnk[u.po]; p; p = e[p].nxt)
        {
            int y = e[p].to;
            if((e[p].tp & u.sta) != e[p].tp) continue;
            if(dis[y][u.sta | key[y]] > dis[u.po][u.sta] + 1)
            {
                dis[y][u.sta | key[y]] = dis[u.po][u.sta] + 1;
                if(!vis[y][u.sta|key[y]]) 
                    vis[y][u.sta|key[y]] = 1, q.push(node(y, u.sta|key[y]));
            }
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &p);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) 
            id[i][j] = ++num;
    scanf("%d", &k);
    for(int i = 1; i <= k; ++i)
    {
        scanf("%d%d%d%d%d", &x1, &yone, &x2, &y2, &g);
        if(g) flo[id[x1][yone]][id[x2][y2]] = flo[id[x2][y2]][id[x1][yone]] = g;
        else flo[id[x1][yone]][id[x2][y2]] = flo[id[x2][y2]][id[x1][yone]] = -1;
    }
    scanf("%d", &s);
    for(int i = 1; i <= s; ++i)
    {
        scanf("%d%d%d", &x1, &yone, &g);
        key[id[x1][yone]] |= (1 << (g - 1));
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            for(int l = 0; l < 4; ++l)
            {
                int ix = i + dx[l], iy = j + dy[l], fl = flo[id[i][j]][id[ix][iy]];
                if(ix < 1 || ix > n || iy < 1 || iy > m || fl == -1) continue;
                if(fl) add(id[i][j], id[ix][iy], 1 << (fl - 1));
                else add(id[i][j], id[ix][iy], 0);
            }
    bfs(); int ans = 0x3f3f3f3f;
    for(int i = 0; i <= (1 << s) - 1; ++i) 
        ans = min(ans, dis[num][i]);
    if(ans < 0x3f3f3f3f) printf("%d\n", ans);
    else puts("-1");
    return 0;
}

LOJ 6122, 最大流

有次数限制? 拆点就好了. 反向不好找? 增广两遍, 改一下首尾限制.

输出……方案……

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <string>
#include <map>
#include <queue>
#include <bitset>

using namespace std;

const int maxn = 110;
const int inf_ = 0x3f3f3f3f;

struct edge
{
    int to, nxt, w, c;
}e[maxn * maxn];
int ptr, lnk[maxn << 1], pre[maxn << 1], id[maxn << 1], dis[maxn << 1];
int n, v, s,t;
string city[maxn];
map<string, int> mp;
bitset<maxn << 1> vis;
queue<int> q;

inline void add(int bgn, int end, int val, int cost)
{
    e[ptr].to = end; e[ptr].w = val; e[ptr].c = cost;
    e[ptr].nxt = lnk[bgn]; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].w = 0; e[ptr].c = -cost;
    e[ptr].nxt = lnk[end]; lnk[end] = ptr; ptr++; 
}
inline bool spfa(int S, int T)
{
    memset(dis, 0, sizeof dis);
    vis.reset(); q.push(S); vis[S] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop(); vis[u] = 0;
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].w && dis[y] < dis[u] + e[p].c)
            {
                dis[y] = dis[u] + e[p].c;
                pre[y] = u;
                id[y] = p;
                if(!vis[y]) vis[y] = 1, q.push(y);
            }
        }
    }
    return dis[T];
}
int cost_flow(int S, int T)
{
    int flow = 0, cost = 0, aug;
    while(spfa(S, T) && flow != 2)
    {
        aug = inf_;
        for(int p = T; p != S; p = pre[p])
            aug = min(aug, e[id[p]].w);
        flow += aug;
        cost += aug * dis[T];
        for(int p = T; p != S; p = pre[p])
            e[id[p]].w -= aug, e[id[p]^1].w += aug;
    }
    return cost;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> v;
    memset(lnk, -1, sizeof lnk);
    s = 1; t = n * 2;
    for(int i = 1; i <= n; ++i)
    {
        cin >> city[i];
        mp[city[i]] = i;
    }
    for(int i = 1; i <= n; ++i)
        add(i, i + n, 1 + (i == 1 || i == n), 1);
    for(int i = 1; i <= v; ++i)
    {
        string x, y; int xx, yy;
        cin >> x >> y;
        xx = mp[x]; yy = mp[y];
        if(xx > yy) swap(xx, yy);
        add(xx + n, yy, 1 + (xx == 1&&yy == n), 0);
 	}
 	int ret = cost_flow(s, t);
 	if(ret == 0) 
 	{
 		puts("No Solution!");
 		return 0;
 	} 
 	cout << ret - 2 << endl;
 	cout << city[1] << endl;
 	vis.reset();
 	int j, k;
 	for(int p = lnk[s + n]; ~p; p = e[p].nxt)
 	{
 		if(!e[p].w && !(p&1))
 		{
 			k = e[p].to;
 			while(k)
 			{
 				cout << city[k] << endl;
 				vis[k] = 1;
 				for(j = lnk[k+n], k = 0; ~j; j = e[j].nxt)
 				{
 					if(!e[j].w && !(j&1))
 					{
 						k = e[j].to; break;
 					}
 				}
 			}
 			break;
 		}
 	}
 	for(int p = lnk[t - n]; ~p ; p = e[p].nxt)
 	{
 		if(!e[p^1].w && (p&1) && !vis[e[p].to - n])
 		{
 			k = e[p].to - n;
 			while(k)
 			{
 				cout << city[k] << endl;
 				for(j = lnk[k], k = 0; ~j; j = e[j].nxt)
 				{
 					if(!e[j^1].w && (j&1))
 					{
 						k = e[j].to - n; break;
 					}
 				}
 			}
 			break;
 		}
 	}
    return 0;
}

LOJ 6223, 分层图最短路

嗯嗯嗯?

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;


const int maxn = 102;
const int maxp = maxn * maxn * 2;
const int maxe = maxp * 20;
const int inf_ = 0x3f3f3f3f;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

struct edge
{
    int to, nxt, v;
}e[maxe];
struct node
{
    int po, res;
    constexpr node(int p_ = 0, int r_ = 0):
    po(p_), res(r_){}
};
int mtr[maxn][maxn], mp[maxn][maxn], num;
int ptr, lnk[maxp], dis[maxp][20], cri[maxp];
int n, k, a, b, c;
bool vis[maxp][20];
queue<node> q;

inline void add(int bgn, int end, int val)
{
    e[++ptr].to = end; e[ptr].nxt = lnk[bgn]; e[ptr].v = val;
    lnk[bgn] = ptr;
}
inline void spfa()
{
    for(int i = 1; i <= num; ++i)
        for(int j = 0; j <= k; ++j)
            dis[i][j] = inf_;
    q.push(node(1, k)); dis[1][k] = 0; vis[1][k] = 1;
    while(!q.empty())
    {
        node u = q.front(); q.pop(); vis[u.po][u.res] = 0;
        if(cri[u.po] && u.res != k)
        {
            if(dis[u.po][k] > dis[u.po][u.res] + a)
            {
                dis[u.po][k] = dis[u.po][u.res] + a;
                if(!vis[u.po][k])
                    vis[u.po][k] = 1, q.push(node(u.po, k));
            }
            continue;
        }
        else
        {
            if(dis[u.po][k] > dis[u.po][u.res] + a + c)
            {
                dis[u.po][k] = dis[u.po][u.res] + a + c;
                if(!vis[u.po][k])
                    vis[u.po][k] = 1, q.push(node(u.po, k));
            }
        }
        if(!u.res) continue;
        for(int p = lnk[u.po]; p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(dis[y][u.res - 1] > dis[u.po][u.res] + e[p].v)
            {
                dis[y][u.res - 1] = dis[u.po][u.res] + e[p].v;
                if(!vis[y][u.res - 1])
                    vis[y][u.res - 1] = 1, q.push(node(y, u.res - 1));
            }
        }
    }
}


int main()
{
    scanf("%d%d%d%d%d", &n, &k, &a, &b, &c);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j) 
            mp[i][j] = ++num;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            scanf("%d", &cri[mp[i][j]]);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            for(int l = 0; l < 4; ++l)
            {
                int ix = i + dx[l], iy = j + dy[l];
                if(ix < 1 || ix > n || iy < 1 || iy > n) continue;
                add(mp[i][j], mp[ix][iy], (dx[l] < 0 || dy[l] < 0) ? b : 0);
            }
    spfa(); int ans = inf_;
    for(int i = 0; i <= k; ++i)
        ans = min(ans, dis[num][i]);
    printf("%d\n", ans);
    return 0;
}

LOJ 6224, 费用流

首次流有费用, 再流没费用, 建两条边.

源连机器人, 目的地连汇.

嘿嘿嘿, 没有方案, 嘿嘿嘿……(精神失常

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <bitset>

using namespace std;

const int maxn = 20;
const int maxp = maxn * maxn << 1;
const int maxe = maxp << 4;
const int inf_ = 0x3f3f3f3f;

struct edge
{
    int to, nxt, w, c;
}e[maxe];
int ptr, lnk[maxp], dis[maxp], pre[maxp], id[maxp];
int p, q, mp[maxn][maxn], a, b, s, t;
bitset<maxp>vis;
queue<int> que;

inline void add(int bgn, int end, int val ,int cost)
{
    e[ptr].to = end; e[ptr].w = val; e[ptr].c = cost; 
    e[ptr].nxt = lnk[bgn]; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].w = 0; e[ptr].c = -cost;
    e[ptr].nxt = lnk[end]; lnk[end] = ptr; ptr++;
} 
inline bool spfa(int S, int T)
{
    for(int i = 0; i <= T; ++i) dis[i] = inf_;
    vis.reset();
    que.push(S); vis[S] = 1; dis[S] = 0;
    while(!que.empty())
    {
        int u = que.front(); que.pop(); vis[u] = 0;
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].w > 0 && dis[u] + e[p].c < dis[y])
            {
                dis[y] = dis[u] + e[p].c;
                pre[y] = u;
                id[y] = p;
                if(!vis[y]) vis[y] = 1, que.push(y);
            }
        }
    }
    return dis[T] < inf_;
}
inline int cost_flow(int S, int T)
{
    int flow = 0, cost = 0, aug;
    while(spfa(S, T))
    {
        aug = inf_;
        for(int p = T; p != S; p = pre[p])
            aug = min(aug, e[id[p]].w);
        cost += aug * dis[T];
        flow += aug;
        for(int p = T; p != S; p = pre[p])
            e[id[p]].w -= aug, e[id[p]^1].w += aug;
    }
    return cost;
} 

int main()
{
    memset(lnk, -1, sizeof lnk);
    scanf("%d%d", &a, &b);
    scanf("%d%d", &p, &q);
    int c = 0, x, y; s = 0; t = (p+1)*(q+1)+1;
    for(int i = 0; i <= p; ++i)
        for(int j = 0; j <= q; ++j)
            mp[i][j] = ++c;
    for(int i = 0; i <= p; ++i)
        for(int j = 0; j < q; ++j)
        {
            scanf("%d", &c);
            add(mp[i][j], mp[i][j+1], 1, -c);
            add(mp[i][j], mp[i][j+1], inf_, 0);
        }
    for(int j = 0; j <= q; ++j)
        for(int i = 0; i < p; ++i)
        {
            scanf("%d", &c);
            add(mp[i][j], mp[i+1][j], 1, -c);
            add(mp[i][j], mp[i+1][j], inf_, 0);
        }
    for(int i = 0; i < a; ++i)
        scanf("%d%d%d", &c, &x, &y), add(s, mp[x][y], c, 0);
    for(int i = 0; i < b; ++i)
        scanf("%d%d%d", &c, &x, &y), add(mp[x][y], t, c, 0);
    int ret = cost_flow(s, t);
    printf("%d\n", -ret);
    return 0;
}

LOJ 6225, 费用流

跟6224差不多.

输出……………….(死亡

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <bitset>
#include <queue>

using namespace std;

const int maxn = 70;
const int maxp = maxn * maxn;
const int inf_ = 0x3f3f3f3f;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct edge
{
    int to, nxt, w, c;
}e[maxn * maxn << 2];
int ptr, lnk[maxp], pre[maxp], id[maxp];
int mp[maxn][maxn];
int dis[maxp];
int n, p, Q, flow, s, t;
int mtr[maxn][maxn], top, rtn[maxn * 2], cnt[maxn * maxn << 2];
bitset<maxp> vis;
queue<int> q;

inline void add(int bgn, int end, int val, int cost)
{
    e[ptr].to = end; e[ptr].w = val; e[ptr].c = cost;
    e[ptr].nxt = lnk[bgn]; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].w = 0; e[ptr].c = -cost;
    e[ptr].nxt = lnk[end]; lnk[end] = ptr; ptr++;
}
inline bool spfa(int S, int T)
{
    for(int i = S; i <= T; ++i) dis[i] = inf_;
    vis.reset(); dis[S] = 0; q.push(S); vis[S] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop(); vis[u] = 0;
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].w && dis[y] > dis[u] + e[p].c)
            {
                dis[y] = dis[u] + e[p].c;
                pre[y] = u;
                id[y] = p;
                if(!vis[y]) vis[y] = 1, q.push(y);
            }
        }
    }
    return dis[T] < inf_;
}
void cost_flow(int S, int T)
{
    int aug;
    while(spfa(S, T))
    {
        aug = inf_;
        for(int p = T; p != S; p = pre[p])
            aug = min(aug, e[id[p]].w);
        flow += aug;
        for(int p = T; p != S; p = pre[p])
            e[id[p]].w -= aug, e[id[p] ^ 1].w += aug;
    }
}
void dfs(int x, int y)
{
    int idx = mp[x][y], sth = mp[x + 1][y], eth = mp[x][y + 1];
    for(int i = lnk[idx + p * Q]; ~i; i = e[i].nxt)
    {
        if(cnt[i] >= e[i^1].w) continue;
        if(e[i].to == sth)
        {
            ++cnt[i]; rtn[++top] = 0;
            dfs(x+1, y);
            return;
        }
        if(e[i].to == eth)
        {
            ++cnt[i]; rtn[++top] = 1;
            dfs(x, y+1);
            return;
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &p, &Q);
    memset(lnk, -1, sizeof lnk);
    s = 0; t = p * Q * 2 + 1;
    for(int i = 1; i <= Q; ++i)
        for(int j = 1; j <= p; ++j) 
            scanf("%d", &mtr[i][j]);
    for(int i = 1; i <= Q; ++i) 
        for(int j = 1; j <= p; ++j) 
            mp[i][j] = (i - 1) * p + j;
    for(int i = 1; i <= Q; ++i)
        for(int j = 1; j <= p; ++j)
        {
            if(mtr[i][j] == 1) continue;
            add(mp[i][j], mp[i][j] + p * Q, inf_, 0);
            if(mtr[i][j] == 0)
            {
                for(int k = 0; k < 2; ++k)
                {
                    int x = i + dx[k], y = j + dy[k];
                    if(x < 1 || x > Q || y < 1 || y > p || mtr[x][y] == 1) continue;
                    add(mp[i][j] + p*Q, mp[x][y], inf_, 0);
                }
            }
            else
            {
                add(mp[i][j], mp[i][j] + p * Q, 1, -1);
                for(int k = 0; k < 2; ++k)
                {
                    int x = i + dx[k], y = j + dy[k];
                    if(x < 1 || x > Q || y < 1 || y > p || mtr[x][y] == 1) continue;
                    add(mp[i][j] + p*Q, mp[x][y], inf_, 0);
                }
            }
        }
    add(s, 1, n, 0); add(p * Q * 2, t, n, 0);
    //while(spfa(s, t));
    cost_flow(s, t);
    for(int i = 1; i <= flow; ++i)
    {
        top = 0; dfs(1, 1);
        for(int j = 1; j <= top; ++j) 
            printf("%d %d\n", i, rtn[j]);
    }
    return 0;
}

LOJ 6226, 最小割

奇偶建图, 跟方格取数差不多, 坏点随便处理一下.

也是减一下.

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>
#include <queue>

using namespace std;

const int maxn = 205;

struct edge
{
    int to, nxt, v;
}e[maxn * maxn * 20];
int n, m, ptr, lnk[maxn * maxn], level[maxn * maxn];
int cur[maxn * maxn];
int x, y, id[maxn][maxn], s, t;
bitset<maxn> nt[maxn];
queue<int> q;
int dx[8] = {2, 2, 1, 1, -2, -2, -1, -1};
int dy[8] = {-1, 1, -2, 2, -1, 1, -2, 2};

inline void add(int bgn, int end, int val)
{
    e[ptr].to = end; e[ptr].nxt = lnk[bgn]; e[ptr].v = val; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].nxt = lnk[end]; e[ptr].v = 0; lnk[end] = ptr; ptr++;
}
bool bfs()
{
    memset(level, 0, sizeof level);
    q.push(s); level[s] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].v > 0 && !level[y])
            {
                q.push(y);
                level[y] = level[u] + 1;
            }
        }
    }
    return level[t] != 0;
}
int dfs(int x, int fl)
{
    if(x == t) return fl;
    for(int &p = cur[x]; ~p; p = e[p].nxt)
    {
        int y = e[p].to;
        if(level[y] == level[x] + 1 && e[p].v)
        {
            int delta = dfs(y, min(fl, e[p].v));
            if(delta > 0)
            {
                e[p].v -= delta;
                e[p^1].v += delta;
                return delta;
            }
        }
    }
    return 0;
}
int dinic()
{
    int ret = 0;
    while(bfs())
    {
        memcpy(cur, lnk, sizeof cur);
        while(int delta = dfs(s, 0x3f3f3f3f + 1))
            ret += delta;
    }
    return ret;
}
int main()
{
    scanf("%d%d", &n, &m);
    memset(lnk, -1, sizeof lnk);
    s = 0; t = n * n + 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            id[i][j] = (i-1)*n + j;
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &x, &y);
        nt[x][y] = 1;        
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            if(nt[i][j]) continue;
            if((i+j) & 1)
            {
                add(s, id[i][j], 1);
                for(int k = 0; k < 8; ++k)
                {
                    int x = i + dx[k], y = j + dy[k];
                    if(x < 1 || x > n || y < 1 || y > n || nt[x][y]) continue;
                    add(id[i][j], id[x][y], 0x3f3f3f3f);
                }
            }
            else add(id[i][j], t, 1);
        }
    int ret = dinic();
    printf("%d\n", n * n - m - ret);
    return 0;
}

LOJ 6227, 费用流

跟区间差不多, 但是有环了?

拆点咯, 保留覆盖次数限制, 强行构造个DAG.

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>

using namespace std;

typedef long long ll;

const int maxn = 2005;
const int inf_ = 0x3f3f3f3f;

struct edge
{
    int to, nxt, w, c;
}e[maxn << 2];
struct line
{
    int x0, y0, x2, y2;
    int len;
    int nx0, nx1;
}l[maxn];
int cpy[maxn], tot, len, dis[maxn], pre[maxn], id[maxn], vis[maxn];
int lnk[maxn], ptr, n, k, s, t;
queue<int> q;

inline void add(int bgn, int end, int val, int cost)
{
    e[ptr].to = end; e[ptr].w = val; e[ptr].c = cost;
    e[ptr].nxt = lnk[bgn]; lnk[bgn] = ptr; ptr++;
    e[ptr].to = bgn; e[ptr].w = 0; e[ptr].c = -cost;
    e[ptr].nxt = lnk[end]; lnk[end] = ptr; ptr++;
}
inline bool spfa()
{
    for(int i = s; i <= t; ++i) dis[i] = inf_;
    memset(vis, 0, sizeof vis); q.push(s); dis[s] = 0; vis[s] = 1;
    while(!q.empty())
    {
        int u = q.front(); q.pop(); vis[u] = 0;
        for(int p = lnk[u]; ~p; p = e[p].nxt)
        {
            int y = e[p].to;
            if(e[p].w && e[p].c + dis[u] < dis[y])
            {
                dis[y] = dis[u] + e[p].c;
                pre[y] = u; id[y] = p;
                if(!vis[y]) vis[y] = 1, q.push(y);
            }
        }
    }
    return dis[t] < inf_;
}
inline int cost_flow()
{
    int flow = 0, cost = 0, aug;
    while(spfa())
    {
        aug = inf_;
        for(int p = t; p != s; p = pre[p])
            aug = min(aug, e[id[p]].w);
        cost += aug * dis[t];
        flow += aug;
        for(int p = t; p != s; p = pre[p])
            e[id[p]].w -= aug, e[id[p]^1].w += aug;
    }
    return cost;
}

int main()
{
    scanf("%d%d", &n, &k);
    memset(lnk, -1, sizeof lnk);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d%d%d%d", &l[i].x0, &l[i].y0, &l[i].x2, &l[i].y2);
        if(l[i].x0 > l[i].x2) swap(l[i].x0, l[i].x2), swap(l[i].y0, l[i].y2);
        cpy[++tot] = l[i].x0; cpy[++tot] = l[i].x2;
        l[i].len = (int)floor(sqrt((ll)(l[i].x0 - l[i].x2)*(l[i].x0 - l[i].x2) + (ll)(l[i].y0 - l[i].y2)*(l[i].y0 - l[i].y2)));
    }
    sort(cpy + 1, cpy + 1 + tot);
    int len = unique(cpy + 1, cpy + 1 + tot) - (cpy + 1);
    for(int i = 1; i <= n; ++i)
    {
        l[i].nx0 = lower_bound(cpy + 1, cpy + 1 + len, l[i].x0) - cpy;
        l[i].nx1 = lower_bound(cpy + 1, cpy + 1 + len, l[i].x2) - cpy;
    }
    s = 0; t = 2 * len + 1;
    for(int i = 1; i <= len; ++i)
        add(i, i + len, inf_, 0);
    add(s, 1, k, 0);
    add(2 * len, t, k, 0);
    for(int i = 1; i < len; ++i)
        add(i + len, i + 1, k, 0);
    for(int i = 1; i <= n; ++i)
    {
        if(l[i].nx0 == l[i].nx1) add(l[i].nx0, l[i].nx1 + len, 1, -l[i].len);
        else add(l[i].nx0 + len, l[i].nx1, 1, -l[i].len);
    }
    int ret = cost_flow();
    printf("%d\n", -ret);
    return 0;
}