【线性规划和网络流24题】

（1）飞行员配对方案问题：二分图最大匹配。

思路：略。

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #define MAXN 1010
 4 int cx[MAXN], cy[MAXN];
 5 int first[MAXN], next[MAXN], v[MAXN], e;
 6 bool vis[MAXN];
 7 inline void addEdge(int x, int y) {
 8     v[e] = y;
 9     next[e] = first[x];
10     first[x] = e++;
11 }
12 int path(int x) {
13     int i;
14     int y;
15     for (i = first[x]; i != -1; i = next[i]) {
16         y = v[i];
17         if (!vis[y]) {
18             vis[y] = true;
19             if (cy[y] == -1 || path(cy[y])) {
20                 cx[x] = y;
21                 cy[y] = x;
22                 return 1;
23             }
24         }
25     }
26     return 0;
27 }
28 int main() {
29     int n, m;
30     int i;
31     int x, y;
32     int ans;
33     while (~scanf("%d%d", &m, &n)) {
34         e = 0;
35         memset(first, -1, sizeof(first));
36         while (scanf("%d%d", &x, &y), x != -1) {
37             addEdge(x, y);
38         }
39         ans = 0;
40         memset(cx, -1, sizeof(cx));
41         memset(cy, -1, sizeof(cy));
42         for (i = 1; i <= m; i++) {
43             memset(vis, false, sizeof(vis));
44             ans += path(i);
45         }
46         if (ans) {
47             printf("%d\n", ans);
48             for (i = 1; i <= m; i++) {
49                 if (cx[i] != -1) {
50                     printf("%d %d\n", i, cx[i]);
51                 }
52             }
53         } else {
54             puts("No Solution!");
55         }
56     }
57     return 0;
58 }

（2）太空飞行计划问题：最大权闭合图。

思路：

1。源向实验连边，流量为收益。

2。仪器向汇连边，流量为消耗。

3。实验向仪器连边，流量为无穷。

4。所有实验的收益-最大流=最大收益。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #include<algorithm>
  5 #include<iostream>
  6 #define MAXL 1010
  7 #define MAXN 100010
  8 #define MAXM 1000010
  9 #define oo 0x7FFFFFFF
 10 using namespace std;
 11 int first[MAXN], next[MAXM], v[MAXM], cost[MAXM], e;
 12 int n;
 13 int src, des;
 14 
 15 bool flag;
 16 bool vis[MAXL];
 17 char str[MAXN];
 18 vector<int> g[MAXL];
 19 vector<int> test;
 20 vector<int> app;
 21 int a[MAXL];
 22 inline void addEdge(int x, int y, int val) {
 23     v[e] = y;
 24     cost[e] = val;
 25     next[e] = first[x];
 26     first[x] = e++;
 27 
 28     v[e] = x;
 29     cost[e] = 0;
 30     next[e] = first[y];
 31     first[y] = e++;
 32 }
 33 int SAP() {
 34     int pre[MAXN], cur[MAXN], dis[MAXN], gap[MAXN];
 35     int flow = 0;
 36     int aug = oo;
 37     int x, y;
 38     bool flag;
 39     for (int i = 0; i < n; i++) {
 40         cur[i] = first[i];
 41         gap[i] = dis[i] = 0;
 42     }
 43     gap[src] = n;
 44     x = pre[src] = src;
 45     while (dis[src] < n) {
 46         flag = false;
 47         for (int &j = cur[x]; j != -1; j = next[j]) {
 48             y = v[j];
 49             if (cost[j] > 0 && dis[x] == dis[y] + 1) {
 50                 flag = true;
 51                 aug = min(aug, cost[j]);
 52                 pre[y] = x;
 53                 x = y;
 54                 if (x == des) {
 55                     flow += aug;
 56                     while (x != src) {
 57                         x = pre[x];
 58                         cost[cur[x]] -= aug;
 59                         cost[cur[x] ^ 1] += aug;
 60                     }
 61                     aug = oo;
 62                 }
 63                 break;
 64             }
 65         }
 66         if (flag) {
 67             continue;
 68         }
 69         int tmp = n;
 70         for (int j = first[x]; j != -1; j = next[j]) {
 71             y = v[j];
 72             if (cost[j] > 0 && dis[y] < tmp) {
 73                 tmp = dis[y];
 74                 cur[x] = j;
 75             }
 76         }
 77         if ((--gap[dis[x]]) == 0) {
 78             break;
 79         }
 80         gap[dis[x] = tmp + 1]++;
 81         x = pre[x];
 82     }
 83     return flow;
 84 }
 85 void out(vector<int> res) {
 86     int i;
 87     sort(res.begin(), res.end());
 88     res.resize(unique(res.begin(), res.end()) - res.begin());
 89     for (i = 0; i < (int) res.size(); i++) {
 90         if (i) {
 91             putchar(' ');
 92         }
 93         printf("%d", res[i]);
 94     }
 95     putchar('\n');
 96 }
 97 void dfs(int x) {
 98     int i;
 99     vis[x] = true;
100     if (x == des) {
101         flag = false;
102     }
103     for (i = first[x]; i != -1; i = next[i]) {
104         if (!vis[v[i]] && cost[i] > 0) {
105             dfs(v[i]);
106         }
107     }
108 }
109 int main() {
110     int m;
111     int i, j, k;
112     int len;
113     int ans;
114     while (~scanf("%d%d", &m, &n)) {
115         src = 0;
116         des = n + m + 1;
117         e = 0;
118         memset(first, -1, sizeof(first));
119         gets(str);
120         for (i = 1; i <= m; i++) {
121             g[i].clear();
122             gets(str);
123             len = strlen(str);
124             for (j = 0; j < len; j++) {
125                 for (; j < len && str[j] == ' '; j++)
126                     ;
127                 if (j < len) {
128                     sscanf(str + j, "%d", &k);
129                     g[i].push_back(k);
130                 }
131                 for (; j < len && isdigit(str[j]); j++)
132                     ;
133             }
134         }
135         for (i = 1; i <= n; i++) {
136             scanf("%d", &a[i]);
137             addEdge(m + i, des, a[i]);
138         }
139         ans = 0;
140         for (i = 1; i <= m; i++) {
141             addEdge(src, i, g[i][0]);
142             ans += g[i][0];
143             for (j = 1; j < (int) g[i].size(); j++) {
144                 addEdge(i, m + g[i][j], oo);
145             }
146         }
147         n = des + 1;
148         ans -= SAP();
149         test.clear();
150         app.clear();
151         for (i = first[src]; i != -1; i = next[i]) {
152             k = v[i];
153             flag = true;
154             memset(vis, false, sizeof(vis));
155             dfs(k);
156             if (flag) {
157                 test.push_back(k);
158                 for (j = 1; j < (int) g[k].size(); j++) {
159                     app.push_back(g[k][j]);
160                 }
161             }
162         }
163         out(test);
164         out(app);
165         printf("%d\n", ans);
166     }
167     return 0;
168 }

（3）最小路径覆盖问题：有向无环图最小路径覆盖。

思路：

1。当原图没有边，增加一条边，就增加一个匹配，显然少了一条路径。

2。当已经有了一个匹配，增加一条边，不会增加匹配数，路径数需增加1。

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #define MAXN 1010
 5 #define MAXM 100010
 6 using namespace std;
 7 int first[MAXN], v[MAXM], next[MAXM], e;
 8 int cx[MAXN], cy[MAXN];
 9 bool vis[MAXN];
10 vector<int> res;
11 inline void addEdge(int x, int y) {
12     next[e] = first[x];
13     v[e] = y;
14     first[x] = e++;
15 }
16 int path(int x) {
17     int i;
18     int y;
19     for (i = first[x]; i != -1; i = next[i]) {
20         y = v[i];
21         if (!vis[y]) {
22             vis[y] = true;
23             if (cy[y] == -1 || path(cy[y])) {
24                 cx[x] = y;
25                 cy[y] = x;
26                 return 1;
27             }
28         }
29     }
30     return 0;
31 }
32 int Match(int n) {
33     int i;
34     int ans = 0;
35     memset(cx, -1, sizeof(cx));
36     memset(cy, -1, sizeof(cy));
37     for (i = 1; i <= n; i++) {
38         memset(vis, false, sizeof(vis));
39         ans += path(i);
40     }
41     return n - ans;
42 }
43 void dfs(int x) {
44     vis[x] = true;
45     res.push_back(x);
46     if (cx[x] != -1) {
47         dfs(cx[x]);
48     }
49 }
50 int main() {
51     int n, m;
52     int i, j;
53     int x, y;
54     int ans;
55     while (~scanf("%d%d", &n, &m)) {
56         e = 0;
57         memset(first, -1, sizeof(first));
58         for (i = 0; i < m; i++) {
59             scanf("%d%d", &x, &y);
60             addEdge(x, y);
61         }
62         ans = Match(n);
63         memset(vis, false, sizeof(vis));
64         for (i = 1; i <= n; i++) {
65             if (!vis[i]) {
66                 res.clear();
67                 dfs(i);
68                 for (j = 0; j < (int) res.size() - 1; j++) {
69                     printf("%d ", res[j]);
70                 }
71                 printf("%d\n", res[j]);
72             }
73         }
74         printf("%d\n", ans);
75     }
76     return 0;
77 }

（4）魔术球问题：有向无环图最小路径覆盖。

思路：

1。若x+y为平方数，则x,y'连一条有向边。

2。递增答案，同时增加新的边，更新二分图的交错路。

3。最小路径覆盖=顶点数-二分图最大匹配。

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #define MAXN 2010
 5 #define MAXM 200010
 6 using namespace std;
 7 int first[MAXN], next[MAXM], v[MAXM], e;
 8 int cx[MAXN], cy[MAXN];
 9 int nx[MAXN];
10 bool vis[MAXN];
11 bool sqr[MAXM];
12 vector<int> res;
13 void init() {
14     int i;
15     memset(sqr, false, sizeof(sqr));
16     for (i = 1; i * i < MAXM; i++) {
17         sqr[i * i] = true;
18     }
19 }
20 inline void addEdge(int x, int y) {
21     v[e] = y;
22     next[e] = first[x];
23     first[x] = e++;
24 }
25 int path(int x) {
26     int i;
27     int y;
28     for (i = first[x]; i != -1; i = next[i]) {
29         y = v[i];
30         if (!vis[y]) {
31             vis[y] = true;
32             if (cy[y] == -1 || path(cy[y])) {
33                 cx[x] = y;
34                 cy[y] = x;
35                 return 1;
36             }
37         }
38     }
39     return 0;
40 }
41 int cal(int n) {
42     int i;
43     int ans;
44     for (i = 1; i < n; i++) {
45         if (sqr[i + n]) {
46             addEdge(i, n);
47         }
48     }
49     ans = 0;
50     for (i = 1; i <= n; i++) {
51         if (cx[i] == -1) {
52             memset(vis, false, sizeof(vis));
53             ans += path(i);
54         } else {
55             ans++;
56         }
57     }
58     return n - ans;
59 }
60 void dfs(int x) {
61     vis[x] = true;
62     res.push_back(x);
63     if (nx[x] != -1) {
64         dfs(nx[x]);
65     }
66 }
67 int main() {
68     int n;
69     int i, j;
70     init();
71     while (~scanf("%d", &n)) {
72         e = 0;
73         memset(first, -1, sizeof(first));
74         memset(cx, -1, sizeof(cx));
75         memset(cy, -1, sizeof(cy));
76         for (i = 1; cal(i) <= n; i++) {
77             memcpy(nx, cx, sizeof(nx));
78         }
79         n = i - 1;
80         printf("%d\n", n);
81         memset(vis, false, sizeof(vis));
82         for (i = 1; i <= n; i++) {
83             if (!vis[i]) {
84                 res.clear();
85                 dfs(i);
86                 for (j = 0; j < (int) res.size() - 1; j++) {
87                     printf("%d ", res[j]);
88                 }
89                 printf("%d\n", res[j]);
90             }
91         }
92     }
93     return 0;
94 }

（5）圆桌问题：二分图多重匹配。

思路：

1。从源点向每个单位连边，流量为单位人数。

2。从每个圆桌向汇点连边，流量为圆桌人数。

3。每个单位向每个圆桌都连边，流量为1。

4。求最大流。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #define MAXN 1010
  5 #define MAXM 1000010
  6 #define oo 0x7FFFFFFF
  7 using namespace std;
  8 int first[MAXN], next[MAXM], v[MAXM], cost[MAXM], e;
  9 int n;
 10 int src, des;
 11 inline void addEdge(int x, int y, int val) {
 12     v[e] = y;
 13     cost[e] = val;
 14     next[e] = first[x];
 15     first[x] = e++;
 16 
 17     v[e] = x;
 18     cost[e] = 0;
 19     next[e] = first[y];
 20     first[y] = e++;
 21 }
 22 int SAP() {
 23     int pre[MAXN], cur[MAXN], dis[MAXN], gap[MAXN];
 24     int flow = 0;
 25     int aug = oo;
 26     int x, y;
 27     bool flag;
 28     for (int i = 0; i < n; i++) {
 29         cur[i] = first[i];
 30         gap[i] = dis[i] = 0;
 31     }
 32     gap[src] = n;
 33     x = pre[src] = src;
 34     while (dis[src] < n) {
 35         flag = false;
 36         for (int &j = cur[x]; j != -1; j = next[j]) {
 37             y = v[j];
 38             if (cost[j] > 0 && dis[x] == dis[y] + 1) {
 39                 flag = true;
 40                 aug = min(aug, cost[j]);
 41                 pre[y] = x;
 42                 x = y;
 43                 if (x == des) {
 44                     flow += aug;
 45                     while (x != src) {
 46                         x = pre[x];
 47                         cost[cur[x]] -= aug;
 48                         cost[cur[x] ^ 1] += aug;
 49                     }
 50                     aug = oo;
 51                 }
 52                 break;
 53             }
 54         }
 55         if (flag) {
 56             continue;
 57         }
 58         int tmp = n;
 59         for (int j = first[x]; j != -1; j = next[j]) {
 60             y = v[j];
 61             if (cost[j] > 0 && dis[y] < tmp) {
 62                 tmp = dis[y];
 63                 cur[x] = j;
 64             }
 65         }
 66         if ((--gap[dis[x]]) == 0) {
 67             break;
 68         }
 69         gap[dis[x] = tmp + 1]++;
 70         x = pre[x];
 71     }
 72     return flow;
 73 }
 74 int main() {
 75     int m;
 76     int i, j;
 77     int tot;
 78     vector<int> res[MAXN];
 79     scanf("%d%d", &m, &n);
 80     src = 0;
 81     des = n + m + 1;
 82     e = 0;
 83     memset(first, -1, sizeof(first));
 84     tot = 0;
 85     for (i = 1; i <= m; i++) {
 86         scanf("%d", &j);
 87         addEdge(src, i, j);
 88         tot += j;
 89     }
 90     for (i = 1; i <= n; i++) {
 91         scanf("%d", &j);
 92         addEdge(m + i, des, j);
 93     }
 94     for (i = 1; i <= m; i++) {
 95         for (j = m + 1; j <= n + m; j++) {
 96             addEdge(i, j, 1);
 97         }
 98     }
 99     n = des + 1;
100     for (i = 0; i < MAXN; i++) {
101         res[i].clear();
102     }
103     if (tot == SAP()) {
104         puts("1");
105         for (i = first[src]; i != -1; i = next[i]) {
106             for (j = first[v[i]]; j != -1; j = next[j]) {
107                 if (cost[j] == 0) {
108                     res[v[i]].push_back(v[j] - m);
109                 }
110             }
111         }
112         for (i = 1; i <= m; i++) {
113             for (j = 0; j < (int) res[i].size() - 1; j++) {
114                 printf("%d ", res[i][j]);
115             }
116             printf("%d\n", res[i][j]);
117         }
118     } else {
119         puts("0");
120     }
121     return 0;
122 }

（6）最长递增子序列问题：最多不相交路径。

思路：

1。对于第一问：dp即可。

2。每个点取的次数有要求，所以需要拆点，限制流量。

3。控制最长递增子序列，要从dp转移来连边。

题目描述有错：应是最长非降子序列，而不是严格递增的。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #define MAXN 10010
  5 #define MAXM 1000010
  6 #define oo 123456789
  7 using namespace std;
  8 int first[MAXN], next[MAXM], v[MAXM], cost[MAXM], e;
  9 int n;
 10 int src, des;
 11 
 12 int dp[MAXN];
 13 int arr[MAXN];
 14 inline void addEdge(int x, int y, int val) {
 15     v[e] = y;
 16     cost[e] = val;
 17     next[e] = first[x];
 18     first[x] = e++;
 19 
 20     v[e] = x;
 21     cost[e] = 0;
 22     next[e] = first[y];
 23     first[y] = e++;
 24 }
 25 int SAP() {
 26     int pre[MAXN], cur[MAXN], dis[MAXN], gap[MAXN];
 27     int flow = 0;
 28     int aug = oo;
 29     int x, y;
 30     bool flag;
 31     for (int i = 0; i < n; i++) {
 32         cur[i] = first[i];
 33         gap[i] = dis[i] = 0;
 34     }
 35     gap[src] = n;
 36     x = pre[src] = src;
 37     while (dis[src] < n) {
 38         flag = false;
 39         for (int &j = cur[x]; j != -1; j = next[j]) {
 40             y = v[j];
 41             if (cost[j] > 0 && dis[x] == dis[y] + 1) {
 42                 flag = true;
 43                 aug = min(aug, cost[j]);
 44                 pre[y] = x;
 45                 x = y;
 46                 if (x == des) {
 47                     flow = min(flow + aug, oo);
 48                     while (x != src) {
 49                         x = pre[x];
 50                         cost[cur[x]] -= aug;
 51                         cost[cur[x] ^ 1] += aug;
 52                     }
 53                     aug = oo;
 54                 }
 55                 break;
 56             }
 57         }
 58         if (flag) {
 59             continue;
 60         }
 61         int tmp = n;
 62         for (int j = first[x]; j != -1; j = next[j]) {
 63             y = v[j];
 64             if (cost[j] > 0 && dis[y] < tmp) {
 65                 tmp = dis[y];
 66                 cur[x] = j;
 67             }
 68         }
 69         if ((--gap[dis[x]]) == 0) {
 70             break;
 71         }
 72         gap[dis[x] = tmp + 1]++;
 73         x = pre[x];
 74     }
 75     return flow;
 76 }
 77 int getIndex(int x) {
 78     return 2 * x - 1;
 79 }
 80 void cal(int len, int val) {
 81     int i, j;
 82     int tmp;
 83     int ans;
 84     e = 0;
 85     memset(first, -1, sizeof(first));
 86     src = 0;
 87     des = 2 * n + 1;
 88     for (i = 1; i <= n; i++) {
 89         if (i == 1 || i == n) {
 90             addEdge(getIndex(i), getIndex(i) + 1, val);
 91         } else {
 92             addEdge(getIndex(i), getIndex(i) + 1, 1);
 93         }
 94     }
 95     for (i = 1; i <= n; i++) {
 96         if (dp[i] == 1) {
 97             addEdge(src, getIndex(i), oo);
 98         }
 99         if (dp[i] == len) {
100             addEdge(getIndex(i) + 1, des, oo);
101         }
102     }
103     for (i = 1; i <= n; i++) {
104         for (j = 1; j < i; j++) {
105             if (arr[i] >= arr[j] && dp[i] == dp[j] + 1) {
106                 addEdge(getIndex(j) + 1, getIndex(i), 1);
107             }
108         }
109     }
110     tmp = n;
111     n = des + 1;
112     ans = SAP();
113     n = tmp;
114     if (ans == oo) {
115         ans = n;
116     }
117     printf("%d\n", ans);
118 }
119 int main() {
120     int i, j;
121     int ans;
122     while (~scanf("%d", &n)) {
123         for (i = 1; i <= n; i++) {
124             scanf("%d", &arr[i]);
125             dp[i] = 1;
126         }
127         for (i = 1; i <= n; i++) {
128             for (j = 1; j < i; j++) {
129                 if (arr[i] >= arr[j]) {
130                     dp[i] = max(dp[i], dp[j] + 1);
131                 }
132             }
133         }
134         ans = 0;
135         for (i = 1; i <= n; i++) {
136             ans = max(ans, dp[i]);
137         }
138         printf("%d\n", ans);
139         cal(ans, 1);
140         cal(ans, oo);
141     }
142     return 0;
143 }

（7）试题库问题：二分图多重匹配。

思路：

1。从源点向每道试题连边，流量为1。

2。从每个类型向汇点连边，流量为每个类型所需要的题数。

3。每个试题向所属的类型都连边，流量为1。

4。求最大流。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #define MAXN 1010
  5 #define MAXM 1000010
  6 #define oo 0x7FFFFFFF
  7 using namespace std;
  8 int first[MAXN], next[MAXM], v[MAXM], cost[MAXM], e;
  9 int n;
 10 int src, des;
 11 inline void addEdge(int x, int y, int val) {
 12     v[e] = y;
 13     cost[e] = val;
 14     next[e] = first[x];
 15     first[x] = e++;
 16 
 17     v[e] = x;
 18     cost[e] = 0;
 19     next[e] = first[y];
 20     first[y] = e++;
 21 }
 22 int SAP() {
 23     int pre[MAXN], cur[MAXN], dis[MAXN], gap[MAXN];
 24     int flow = 0;
 25     int aug = oo;
 26     int x, y;
 27     bool flag;
 28     for (int i = 0; i < n; i++) {
 29         cur[i] = first[i];
 30         gap[i] = dis[i] = 0;
 31     }
 32     gap[src] = n;
 33     x = pre[src] = src;
 34     while (dis[src] < n) {
 35         flag = false;
 36         for (int &j = cur[x]; j != -1; j = next[j]) {
 37             y = v[j];
 38             if (cost[j] > 0 && dis[x] == dis[y] + 1) {
 39                 flag = true;
 40                 aug = min(aug, cost[j]);
 41                 pre[y] = x;
 42                 x = y;
 43                 if (x == des) {
 44                     flow += aug;
 45                     while (x != src) {
 46                         x = pre[x];
 47                         cost[cur[x]] -= aug;
 48                         cost[cur[x] ^ 1] += aug;
 49                     }
 50                     aug = oo;
 51                 }
 52                 break;
 53             }
 54         }
 55         if (flag) {
 56             continue;
 57         }
 58         int tmp = n;
 59         for (int j = first[x]; j != -1; j = next[j]) {
 60             y = v[j];
 61             if (cost[j] > 0 && dis[y] < tmp) {
 62                 tmp = dis[y];
 63                 cur[x] = j;
 64             }
 65         }
 66         if ((--gap[dis[x]]) == 0) {
 67             break;
 68         }
 69         gap[dis[x] = tmp + 1]++;
 70         x = pre[x];
 71     }
 72     return flow;
 73 }
 74 int main() {
 75     int m;
 76     int i, j, k;
 77     int tot;
 78     vector<int> res[MAXN];
 79     while (~scanf("%d%d", &m, &n)) {
 80         tot = 0;
 81         src = 0;
 82         des = m + n + 1;
 83         e = 0;
 84         memset(first, -1, sizeof(first));
 85         for (i = 1; i <= m; i++) {
 86             scanf("%d", &j);
 87             addEdge(n + i, des, j);
 88             tot += j;
 89         }
 90         for (i = 1; i <= n; i++) {
 91             scanf("%d", &j);
 92             addEdge(src, i, 1);
 93             while (j--) {
 94                 scanf("%d", &k);
 95                 addEdge(i, n + k, 1);
 96             }
 97         }
 98         k = n;
 99         n = des + 1;
100         if (SAP() == tot) {
101             for (i = 0; i < MAXN; i++) {
102                 res[i].clear();
103             }
104             for (i = first[src]; i != -1; i = next[i]) {
105                 for (j = first[v[i]]; j != -1; j = next[j]) {
106                     if (cost[j] == 0) {
107                         if (v[j] > k)
108                             res[v[j] - k].push_back(v[i]);
109                     }
110                 }
111             }
112             for (i = 1; i <= m; i++) {
113                 printf("%d:", i);
114                 for (j = 0; j < (int) res[i].size(); j++) {
115                     printf(" %d", res[i][j]);
116                 }
117                 putchar('\n');
118             }
119         } else {
120             puts("No Solution!");
121         }
122     }
123     return 0;
124 }

（9）方格取数问题：二分图点权最大独立集。

思路：

1。方格黑白染色。源向黑格连边，流量为点权；白格向汇连边，流量为点权；黑格与相邻的白格连边，流量为oo。因此，最小割是简单割，即最小权覆盖集。

2。由于独立集与覆盖集是互补的，所以最小权覆盖集+最大权独立集=总权值。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #define MAXL 210
  5 #define MAXN 100010
  6 #define MAXM 1000010
  7 #define oo 123456789
  8 using namespace std;
  9 int first[MAXN], next[MAXM], v[MAXM], cost[MAXM], e;
 10 int n, m;
 11 int src, des;
 12 int arr[MAXL][MAXL];
 13 int go[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
 14 inline void addEdge(int x, int y, int val) {
 15     v[e] = y;
 16     cost[e] = val;
 17     next[e] = first[x];
 18     first[x] = e++;
 19 
 20     v[e] = x;
 21     cost[e] = 0;
 22     next[e] = first[y];
 23     first[y] = e++;
 24 }
 25 int SAP() {
 26     int pre[MAXN], cur[MAXN], dis[MAXN], gap[MAXN];
 27     int flow = 0;
 28     int aug = oo;
 29     int x, y;
 30     bool flag;
 31     for (int i = 0; i < n; i++) {
 32         cur[i] = first[i];
 33         gap[i] = dis[i] = 0;
 34     }
 35     gap[src] = n;
 36     x = pre[src] = src;
 37     while (dis[src] < n) {
 38         flag = false;
 39         for (int &j = cur[x]; j != -1; j = next[j]) {
 40             y = v[j];
 41             if (cost[j] > 0 && dis[x] == dis[y] + 1) {
 42                 flag = true;
 43                 aug = min(aug, cost[j]);
 44                 pre[y] = x;
 45                 x = y;
 46                 if (x == des) {
 47                     flow += aug;
 48                     while (x != src) {
 49                         x = pre[x];
 50                         cost[cur[x]] -= aug;
 51                         cost[cur[x] ^ 1] += aug;
 52                     }
 53                     aug = oo;
 54                 }
 55                 break;
 56             }
 57         }
 58         if (flag) {
 59             continue;
 60         }
 61         int tmp = n;
 62         for (int j = first[x]; j != -1; j = next[j]) {
 63             y = v[j];
 64             if (cost[j] > 0 && dis[y] < tmp) {
 65                 tmp = dis[y];
 66                 cur[x] = j;
 67             }
 68         }
 69         if ((--gap[dis[x]]) == 0) {
 70             break;
 71         }
 72         gap[dis[x] = tmp + 1]++;
 73         x = pre[x];
 74     }
 75     return flow;
 76 }
 77 int getIndex(int x, int y) {
 78     return (x - 1) * m + y;
 79 }
 80 int main() {
 81     int i, j, k;
 82     int x, y;
 83     int ans;
 84     while (~scanf("%d%d", &n, &m)) {
 85         src = 0;
 86         des = m * n + 1;
 87         e = 0;
 88         memset(first, -1, sizeof(first));
 89         ans = 0;
 90         for (i = 1; i <= n; i++) {
 91             for (j = 1; j <= m; j++) {
 92                 scanf("%d", &arr[i][j]);
 93                 ans += arr[i][j];
 94                 if ((i + j) & 1) {
 95                     addEdge(src, getIndex(i, j), arr[i][j]);
 96                     for (k = 0; k < 4; k++) {
 97                         x = i + go[k][0];
 98                         y = j + go[k][1];
 99                         if (x > 0 && x <= n && y > 0 && y <= m) {
100                             addEdge(getIndex(i, j), getIndex(x, y), oo);
101                         }
102                     }
103                 } else {
104                     addEdge(getIndex(i, j), des, arr[i][j]);
105                 }
106             }
107         }
108         n = des + 1;
109         ans = ans - SAP();
110         printf("%d\n", ans);
111     }
112     return 0;
113 }

（10）餐巾计划问题：线性规划网络优化。

思路：

1。由于第i天的新餐巾可以由i-m天的脏餐巾洗来，因此考虑按天数建模。

2。每天的餐巾有新旧之分，则考虑拆点，每天的新餐巾数量和每天的旧餐巾数量。

3。新餐巾可以直接买来。

4。新餐巾可以由前些天的旧餐巾洗来。

5。旧餐巾可以由上一天的旧餐巾积累而来。

6。求最小费用最大流。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<algorithm>
  5 #define oo 123456
  6 #define MAXN 100010
  7 #define MAXM 1000010
  8 using namespace std;
  9 int V, e;
 10 int src, des;
 11 int lk[MAXN], father[MAXN];
 12 int first[MAXN], cost[MAXM], flow[MAXM], next[MAXM], v[MAXM];
 13 int dis[MAXN];
 14 bool inq[MAXN];
 15 
 16 int arr[MAXN];
 17 void addEdge(int x, int y, int f, int c) {
 18     v[e] = y;
 19     flow[e] = f;
 20     cost[e] = c;
 21     next[e] = first[x];
 22     first[x] = e++;
 23 
 24     v[e] = x;
 25     flow[e] = 0;
 26     cost[e] = -c;
 27     next[e] = first[y];
 28     first[y] = e++;
 29 }
 30 bool SPFA() {
 31     int i, u;
 32     deque<int> q;
 33     memset(inq, false, sizeof(inq));
 34     for (i = 0; i <= V; i++) {
 35         dis[i] = oo;
 36     }
 37     dis[src] = 0;
 38     q.push_back(src);
 39     inq[src] = true;
 40     while (!q.empty()) {
 41         u = q.front();
 42         q.pop_front();
 43         inq[u] = false;
 44         for (i = first[u]; i != -1; i = next[i]) {
 45             if (flow[i] && dis[v[i]] > dis[u] + cost[i]) {
 46                 dis[v[i]] = dis[u] + cost[i];
 47                 father[v[i]] = u;
 48                 lk[v[i]] = i;
 49                 if (!inq[v[i]]) {
 50                     inq[v[i]] = true;
 51                     if (!q.empty() && dis[v[i]] <= dis[q.front()]) {
 52                         q.push_front(v[i]);
 53                     } else {
 54                         q.push_back(v[i]);
 55                     }
 56                 }
 57             }
 58         }
 59     }
 60     return dis[des] != oo;
 61 }
 62 int MinCostMaxFlow() {
 63     int u;
 64     int ans;
 65     int tmp;
 66     for (ans = 0; SPFA();) {
 67         tmp = oo;
 68         for (u = des; u; u = father[u]) {
 69             tmp = min(tmp, flow[lk[u]]);
 70         }
 71         for (u = des; u; u = father[u]) {
 72             flow[lk[u]] -= tmp;
 73             flow[lk[u] ^ 1] += tmp;
 74         }
 75         ans += tmp * dis[des];
 76     }
 77     return ans;
 78 }
 79 int main() {
 80     int i;
 81     int n;
 82     int buy, fastCost, slowCost, slowDay, fastDay;
 83     while (~scanf("%d%d%d%d%d%d", &n, &buy, &fastDay, &fastCost, &slowDay,
 84             &slowCost)) {
 85         e = 0;
 86         src = 0;
 87         des = n + n + 1;
 88         V = des;
 89         memset(first, -1, sizeof(first));
 90         for (i = 1; i <= n; i++) {
 91             scanf("%d", &arr[i]);
 92             addEdge(2 * i, des, arr[i], 0);
 93             addEdge(src, 2 * i, arr[i], buy);
 94             addEdge(src, 2 * i - 1, arr[i], 0);
 95         }
 96         for (i = 2; i <= n; i++) {
 97             addEdge(2 * (i - 1) - 1, 2 * i - 1, oo, 0);
 98         }
 99         for (i = 1; i <= n; i++) {
100             if (i + fastDay <= n) {
101                 addEdge(2 * i - 1, 2 * (i + fastDay), oo, fastCost);
102             }
103             if (i + slowDay <= n) {
104                 addEdge(2 * i - 1, 2 * (i + slowDay), oo, slowCost);
105             }
106         }
107         for (i = 1; i <= n; i++) {
108             addEdge(src, i, oo, buy);
109         }
110         printf("%d\n", MinCostMaxFlow());
111     }
112     return 0;
113 }

（11）航空路线问题：最长不相交路径。

思路：

1。从东->西，再从西->东。相当于从东->西两条不相交的路径。

2。要求路径最长，则考虑最大费用最大流。

View Code

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<string>
  4 #include<cstring>
  5 #include<queue>
  6 #include<vector>
  7 #include<map>
  8 #define oo 0x7FFFFFFF
  9 #define MAXL 110
 10 #define MAXN 10010
 11 #define MAXM 1000010
 12 using namespace std;
 13 int V, n, m, e;
 14 int src, des;
 15 int lk[MAXN], father[MAXN];
 16 int first[MAXN], cost[MAXM], flow[MAXM], next[MAXM], v[MAXM];
 17 int dis[MAXN];
 18 bool inq[MAXN];
 19 
 20 vector<string> city;
 21 map<string, int> mymap;
 22 vector<int> res;
 23 bool g[MAXL][MAXL];
 24 bool vis[MAXN];
 25 void addEdge(int x, int y, int f, int c) {
 26     v[e] = y;
 27     flow[e] = f;
 28     cost[e] = c;
 29     next[e] = first[x];
 30     first[x] = e++;
 31 
 32     v[e] = x;
 33     flow[e] = 0;
 34     cost[e] = -c;
 35     next[e] = first[y];
 36     first[y] = e++;
 37 }
 38 bool SPFA() {
 39     int i, u;
 40     deque<int> q;
 41     memset(inq, false, sizeof(inq));
 42     for (i = 0; i <= V; i++) {
 43         dis[i] = oo;
 44     }
 45     dis[src] = 0;
 46     q.push_back(src);
 47     inq[src] = true;
 48     while (!q.empty()) {
 49         u = q.front();
 50         q.pop_front();
 51         inq[u] = false;
 52         for (i = first[u]; i != -1; i = next[i]) {
 53             if (flow[i] && dis[v[i]] > dis[u] + cost[i]) {
 54                 dis[v[i]] = dis[u] + cost[i];
 55                 father[v[i]] = u;
 56                 lk[v[i]] = i;
 57                 if (!inq[v[i]]) {
 58                     inq[v[i]] = true;
 59                     if (!q.empty() && dis[v[i]] <= dis[q.front()]) {
 60                         q.push_front(v[i]);
 61                     } else {
 62                         q.push_back(v[i]);
 63                     }
 64                 }
 65             }
 66         }
 67     }
 68     return dis[des] != oo;
 69 }
 70 int MinCostMaxFlow(int tot) {
 71     int u;
 72     int ans;
 73     int tmp;
 74     int flux;
 75     for (ans = flux = 0; SPFA();) {
 76         tmp = oo;
 77         for (u = des; u; u = father[u]) {
 78             tmp = min(tmp, flow[lk[u]]);
 79         }
 80         for (u = des; u; u = father[u]) {
 81             flow[lk[u]] -= tmp;
 82             flow[lk[u] ^ 1] += tmp;
 83         }
 84         ans += tmp * dis[des];
 85         flux += tmp;
 86     }
 87     if (flux != tot) {
 88         return oo;
 89     } else {
 90         return ans;
 91     }
 92 }
 93 void dfs(int x) {
 94     vis[x] = true;
 95     int i;
 96     res.push_back(x >> 1);
 97     for (i = first[x]; i != -1; i = next[i]) {
 98         if ((i & 1) == 0 && flow[i] == 0 && !vis[v[i]]) {
 99             dfs(v[i]);
100         }
101     }
102 }
103 int main() {
104     int i, j;
105     string str1, str2;
106     int ans;
107     bool flag;
108     while (cin >> n >> m) {
109         memset(g, false, sizeof(g));
110         src = 0;
111         des = n + n - 1;
112         V = des;
113         e = 0;
114         memset(first, -1, sizeof(first));
115         city.clear();
116         mymap.clear();
117         addEdge(0, 1, 2, 0);
118         addEdge(des - 1, des, 2, 0);
119         for (i = 2; i < des - 1; i += 2) {
120             addEdge(i, i + 1, 1, 0);
121         }
122         for (i = 0; i < n; i++) {
123             cin >> str1;
124             city.push_back(str1);
125             mymap[str1] = i << 1;
126         }
127         while (m--) {
128             cin >> str1 >> str2;
129             i = mymap[str1];
130             j = mymap[str2];
131             if (i > j) {
132                 swap(i, j);
133             }
134             addEdge(i ^ 1, j, 1, -1);
135             g[i / 2][j / 2] = g[j / 2][i / 2] = true;
136         }
137         ans = MinCostMaxFlow(2);
138         if (ans == oo) {
139             if (g[0][n - 1]) {
140                 cout << 2 << endl;
141                 cout << city[0] << endl;
142                 cout << city[n - 1] << endl;
143                 cout << city[0] << endl;
144             } else {
145                 cout << "No Solution!" << endl;
146             }
147         } else {
148             cout << -ans << endl;
149             memset(vis, false, sizeof(vis));
150             flag = false;
151             cout << city[0] << endl;
152             for (i = first[1]; i != -1; i = next[i]) {
153                 if ((i & 1) == 0 && flow[i] == 0 && !vis[v[i]]) {
154                     res.clear();
155                     dfs(v[i]);
156                     if (flag) {
157                         reverse(res.begin(), res.end());
158                     } else {
159                         flag = true;
160                     }
161                     res.resize(unique(res.begin(), res.end()) - res.begin());
162                     for (j = 0; j < (int) res.size(); j++) {
163                         cout << city[res[j]] << endl;
164                     }
165                 }
166             }
167             cout << city[0] << endl;
168         }
169     }
170     return 0;
171 }

（12）软件补丁问题：最小转移代价。

思路：

1。只有20个补丁，很容易想到状态压缩。

2。最多(1<<20)个状态，一个状态到另一个状态间有一个花费。

3。求最短花费，就是最短路了。

题目描述有错：第二个字符串中'-'是f1的，'+'是f2的。

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #define oo 0x7FFFFFFF
 5 #define MAXN 1<<20
 6 #define MAXM 110
 7 using namespace std;
 8 int dis[MAXN];
 9 bool inq[MAXN];
10 struct patch {
11     int b1, b2;
12     int f1, f2;
13     int cost;
14 } p[MAXM];
15 int n, m;
16 void update(char str[], int &x, int &y) {
17     int i;
18     x = y = 0;
19     for (i = 0; str[i]; i++) {
20         if (str[i] == '+') {
21             x |= 1 << i;
22         } else if (str[i] == '-') {
23             y |= 1 << i;
24         }
25     }
26 }
27 void spfa(int src) {
28     int i;
29     int x, y;
30     deque<int> q;
31     memset(inq, false, sizeof(inq));
32     for (i = 0; i < (1 << n); i++) {
33         dis[i] = oo;
34     }
35     dis[src] = 0;
36     q.push_back(src);
37     while (!q.empty()) {
38         x = q.front();
39         q.pop_front();
40         inq[x] = false;
41         for (i = 0; i < m; i++) {
42             if ((x | p[i].b1) == x && (x & p[i].b2) == 0) {
43                 y = x & (~p[i].f1);
44                 y |= p[i].f2;
45                 if (dis[y] > dis[x] + p[i].cost) {
46                     dis[y] = dis[x] + p[i].cost;
47                     if (!inq[y]) {
48                         if (!q.empty() && dis[y] <= dis[q.front()]) {
49                             q.push_front(y);
50                         } else {
51                             q.push_back(y);
52                         }
53                         inq[y] = true;
54                     }
55                 }
56             }
57         }
58     }
59 }
60 int main() {
61     int i;
62     char a[MAXM], b[MAXM];
63     while (~scanf("%d%d", &n, &m)) {
64         for (i = 0; i < m; i++) {
65             scanf("%d %s %s", &p[i].cost, a, b);
66             update(a, p[i].b1, p[i].b2);
67             update(b, p[i].f2, p[i].f1);
68         }
69         spfa((1 << n) - 1);
70         if (dis[0] == oo) {
71             puts("0");
72         } else {
73             printf("%d\n", dis[0]);
74         }
75     }
76     return 0;
77 }

（13）星际转移问题：网络判定。

思路：

1。枚举天数。随着天数的增加，不断增加点和边。

2。判最大流是否大于等于K。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<vector>
  5 #define oo 123456
  6 #define MAXN 1010
  7 #define MAXM 100010
  8 using namespace std;
  9 int src;
 10 int des;
 11 int V;
 12 int ans;
 13 vector<int> path[MAXN];
 14 vector<int> cap;
 15 vector<int> ind[MAXN];
 16 vector<int> pos[MAXN];
 17 int G[MAXN][MAXN];
 18 int first[MAXN], next[MAXN], v[MAXN], e;
 19 bool vis[MAXN];
 20 int BFS() {
 21     queue<int> q;
 22     int tmp, i, u, v, head, p[MAXN];
 23     memset(p, -1, sizeof(p));
 24     p[src] = src;
 25     q.push(src);
 26     while (!q.empty()) {
 27         head = q.front();
 28         q.pop();
 29         for (i = 1; i <= V; i++) {
 30             if (G[head][i] > 0 && p[i] == -1) {
 31                 p[i] = head;
 32                 q.push(i);
 33             }
 34         }
 35     }
 36     if (p[des] == -1)
 37         return 0;
 38     for (tmp = oo, u = des; p[u] != u;) {
 39         v = u;
 40         u = p[u];
 41         tmp = min(tmp, G[u][v]);
 42     }
 43     for (u = des; p[u] != u;) {
 44         v = u;
 45         u = p[u];
 46         G[u][v] -= tmp;
 47         G[v][u] += tmp;
 48     }
 49     return tmp;
 50 }
 51 void EdmondsKarp() {
 52     int tmp;
 53     for (; (tmp = BFS()); ans += tmp)
 54         ;
 55 }
 56 inline void addEdge(int x, int y) {
 57     next[e] = first[x];
 58     v[e] = y;
 59     first[x] = e++;
 60 }
 61 bool dfs(int x) {
 62     int i;
 63     int y;
 64     vis[x] = true;
 65     for (i = first[x]; i != -1; i = next[i]) {
 66         y = v[i];
 67         if (!vis[y]) {
 68             if (dfs(y)) {
 69                 return true;
 70             }
 71         }
 72     }
 73     return x == des;
 74 }
 75 int main() {
 76     int n, m, k;
 77     int i, j, t;
 78     int tmp;
 79     int day;
 80     int tot;
 81     while (~scanf("%d%d%d", &n, &m, &k)) {
 82         cap.clear();
 83         for (i = 0; i < m; i++) {
 84             scanf("%d%d", &j, &tmp);
 85             cap.push_back(j);
 86             while (tmp--) {
 87                 scanf("%d", &j);
 88                 j += 3;
 89                 path[i].push_back(j);
 90             }
 91         }
 92         src = 3;
 93         des = 2;
 94         e = 0;
 95         memset(first, -1, sizeof(first));
 96         memset(vis, false, sizeof(vis));
 97         for (i = 0; i < m; i++) {
 98             for (j = 0; j < (int) path[i].size(); j++) {
 99                 addEdge(path[i][j], path[i][(j + 1) % path[i].size()]);
100                 addEdge(path[i][j + 1] % path[i].size(), path[i][j]);
101             }
102         }
103         if (dfs(src)) {
104             ans = 0;
105             memset(G, 0, sizeof(G));
106             src = 0;
107             des = 1;
108             tot = 2;
109             for (i = 0; i < m; i++) {
110                 ind[i].clear();
111                 pos[i].clear();
112                 ind[i].push_back(tot++);
113                 pos[i].push_back(path[i][0]);
114             }
115             for (i = 0; i < m; i++) {
116                 if (pos[i][0] == 3) {
117                     G[src][ind[i][0]] = oo;
118                 } else if (pos[i][0] == 2) {
119                     G[ind[i][0]][des] = oo;
120                 }
121             }
122             for (day = 1; ans < k; day++) {
123                 for (i = 0; i < m; i++) {
124                     ind[i].push_back(tot++);
125                     pos[i].push_back(path[i][day % (path[i].size())]);
126                     G[ind[i][day - 1]][ind[i][day]] = cap[i];
127                 }
128                 for (i = 0; i < m; i++) {
129                     for (j = 0; j < m; j++) {
130                         for (t = 0; t <= day; t++) {
131                             if (pos[j][t] == pos[i][day]) {
132                                 G[ind[j][t]][ind[i][day]] = oo;
133                             }
134                         }
135                     }
136                 }
137                 for (i = 0; i < m; i++) {
138                     if (pos[i][day] == 3) {
139                         G[src][ind[i][day]] = oo;
140                     } else if (pos[i][day] == 2) {
141                         G[ind[i][day]][des] = oo;
142                     }
143                 }
144                 V = tot;
145                 EdmondsKarp();
146             }
147             printf("%d\n", day - 1);
148         } else {
149             puts("0");
150         }
151     }
152     return 0;
153 }

（14）孤岛营救问题：分层图最短路径。

思路：

对钥匙种类状态压缩。dp[i][j][k]表示在(i,j)，钥匙种类为k的最短路。

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #define MAXN 11
 5 #define oo 123456789
 6 using namespace std;
 7 int dp[MAXN][MAXN][1 << MAXN];
 8 int g[MAXN][MAXN][MAXN][MAXN];
 9 int mp[MAXN][MAXN];
10 int go[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
11 struct node {
12     int x;
13     int y;
14     int key;
15     int dis;
16 };
17 int n, m, p;
18 inline bool canMove(int x0, int y0, int x1, int y1, int key) {
19     int tmp = g[x0][y0][x1][y1];
20     if (tmp == -1) {
21         return true;
22     } else if (tmp == 0) {
23         return false;
24     } else if (key & (1 << (tmp - 1))) {
25         return true;
26     } else {
27         return false;
28     }
29 }
30 int bfs() {
31     node head, tmp;
32     queue<node> q;
33     int ans;
34     int i, j, k;
35     for (i = 1; i <= n; i++) {
36         for (j = 1; j <= m; j++) {
37             for (k = 0; k < (1 << p); k++)
38                 dp[i][j][k] = oo;
39         }
40     }
41     head.x = head.y = 1;
42     head.key = 0;
43     head.dis = 0;
44     q.push(head);
45     while (!q.empty()) {
46         head = q.front();
47         q.pop();
48         for (i = 0; i < 4; i++) {
49             tmp.x = head.x + go[i][0];
50             tmp.y = head.y + go[i][1];
51             if (tmp.x > 0 && tmp.x <= n && tmp.y > 0 && tmp.y <= m
52                     && canMove(head.x, head.y, tmp.x, tmp.y, head.key)) {
53                 tmp.dis = head.dis + 1;
54                 tmp.key = head.key;
55                 tmp.key |= mp[tmp.x][tmp.y];
56                 if (tmp.dis < dp[tmp.x][tmp.y][tmp.key]) {
57                     dp[tmp.x][tmp.y][tmp.key] = tmp.dis;
58                     q.push(tmp);
59                 }
60             }
61         }
62     }
63     ans = oo;
64     for (i = 0; i < (1 << p); i++) {
65         ans = min(ans, dp[n][m][i]);
66     }
67     if (ans == oo) {
68         return -1;
69     } else {
70         return ans;
71     }
72 }
73 int main() {
74     int i, j;
75     int x0, y0, x1, y1;
76     while (~scanf("%d%d%d", &n, &m, &p)) {
77         memset(g, -1, sizeof(g));
78         memset(mp, 0, sizeof(mp));
79         scanf("%d", &i);
80         while (i--) {
81             scanf("%d%d%d%d%d", &x0, &y0, &x1, &y1, &j);
82             g[x0][y0][x1][y1] = g[x1][y1][x0][y0] = j;
83         }
84         scanf("%d", &i);
85         while (i--) {
86             scanf("%d%d%d", &x0, &y0, &j);
87             mp[x0][y0] |= 1 << (j - 1);
88         }
89         printf("%d\n", bfs());
90     }
91     return 0;
92 }

（15）汽车加油行驶问题：分层图最短路径。

思路：

dp[i][j][k]表示在(i,j)，油量为k的最少花费。

View Code

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #define MAXN 110
 5 #define MAXM 15
 6 #define oo 123456789
 7 using namespace std;
 8 int dp[MAXN][MAXN][MAXM];
 9 int n, k, a, b, c;
10 int g[MAXN][MAXN];
11 struct node {
12     int x;
13     int y;
14     int gass;
15     int cost;
16 };
17 int go[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
18 int spfa() {
19     int i, j, l;
20     int ans;
21     node head, tmp;
22     queue<node> q;
23     for (i = 0; i <= n; i++) {
24         for (j = 0; j <= n; j++) {
25             for (l = 0; l <= k; l++) {
26                 dp[i][j][l] = oo;
27             }
28         }
29     }
30     dp[1][1][k] = 0;
31     head.x = head.y = 1;
32     head.gass = k;
33     head.cost = 0;
34     q.push(head);
35     while (!q.empty()) {
36         head = q.front();
37         q.pop();
38         if (head.gass == 0) {
39             continue;
40         }
41         for (i = 0; i < 4; i++) {
42             tmp.x = head.x + go[i][0];
43             tmp.y = head.y + go[i][1];
44             if (tmp.x > 0 && tmp.x <= n && tmp.y > 0 && tmp.y <= n) {
45                 tmp.gass = head.gass - 1;
46                 tmp.cost = head.cost;
47                 if (tmp.x < head.x || tmp.y < head.y) {
48                     tmp.cost += b;
49                 }
50                 if (g[tmp.x][tmp.y]) {
51                     tmp.gass = k;
52                     tmp.cost += a;
53                 }
54                 if (tmp.cost < dp[tmp.x][tmp.y][tmp.gass]) {
55                     dp[tmp.x][tmp.y][tmp.gass] = tmp.cost;
56                     q.push(tmp);
57                 }
58                 if (!g[tmp.x][tmp.y]) {
59                     tmp.gass = k;
60                     tmp.cost += a + c;
61                     if (tmp.cost < dp[tmp.x][tmp.y][tmp.gass]) {
62                         dp[tmp.x][tmp.y][tmp.gass] = tmp.cost;
63                         q.push(tmp);
64                     }
65                 }
66             }
67         }
68     }
69     ans = oo;
70     for (i = 0; i <= k; i++) {
71         ans = min(ans, dp[n][n][i]);
72     }
73     return ans;
74 }
75 int main() {
76     int i, j;
77     while (~scanf("%d%d%d%d%d", &n, &k, &a, &b, &c)) {
78         for (i = 1; i <= n; i++) {
79             for (j = 1; j <= n; j++) {
80                 scanf("%d", &g[i][j]);
81             }
82         }
83         printf("%d\n", spfa());
84     }
85     return 0;
86 }

（16）数字梯形问题：最大权不相交路径。

思路：

规则1：拆点，点与点之间流量都为1。

规则2：不拆点，点与点流量为1。

规则3：不拆点，点与点流量为无穷。

添加源点，汇点。求最小费用最大流。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<vector>
  5 #define oo 0x7FFFFFFF
  6 #define MAXN 10010
  7 #define MAXM 1000010
  8 using namespace std;
  9 int V, n, m, e;
 10 int src, des;
 11 int link[MAXN], father[MAXN];
 12 int first[MAXN], cost[MAXM], flow[MAXM], next[MAXM], v[MAXM];
 13 int dis[MAXN];
 14 bool inq[MAXN];
 15 
 16 vector<int> arr[MAXN];
 17 vector<int> pos[MAXN];
 18 int size;
 19 void addEdge(int x, int y, int f, int c) {
 20     v[e] = y;
 21     flow[e] = f;
 22     cost[e] = c;
 23     next[e] = first[x];
 24     first[x] = e++;
 25 
 26     v[e] = x;
 27     flow[e] = 0;
 28     cost[e] = -c;
 29     next[e] = first[y];
 30     first[y] = e++;
 31 }
 32 bool SPFA() {
 33     int i, u;
 34     deque<int> q;
 35     memset(inq, false, sizeof(inq));
 36     for (i = 0; i <= V; i++) {
 37         dis[i] = oo;
 38     }
 39     dis[src] = 0;
 40     q.push_back(src);
 41     inq[src] = true;
 42     while (!q.empty()) {
 43         u = q.front();
 44         q.pop_front();
 45         inq[u] = false;
 46         for (i = first[u]; i != -1; i = next[i]) {
 47             if (flow[i] && dis[v[i]] > dis[u] + cost[i]) {
 48                 dis[v[i]] = dis[u] + cost[i];
 49                 father[v[i]] = u;
 50                 link[v[i]] = i;
 51                 if (!inq[v[i]]) {
 52                     inq[v[i]] = true;
 53                     if (!q.empty() && dis[v[i]] <= dis[q.front()]) {
 54                         q.push_front(v[i]);
 55                     } else {
 56                         q.push_back(v[i]);
 57                     }
 58                 }
 59             }
 60         }
 61     }
 62     return dis[des] != oo;
 63 }
 64 int MinCostMaxFlow() {
 65     int u;
 66     int ans;
 67     int tmp;
 68     for (ans = 0; SPFA();) {
 69         tmp = oo;
 70         for (u = des; u; u = father[u]) {
 71             tmp = min(tmp, flow[link[u]]);
 72         }
 73         for (u = des; u; u = father[u]) {
 74             flow[link[u]] -= tmp;
 75             flow[link[u] ^ 1] += tmp;
 76         }
 77         ans += tmp * dis[des];
 78     }
 79     return ans;
 80 }
 81 int getIndex(int x) {
 82     return 2 * x - 1;
 83 }
 84 void rule1() {
 85     int i, j;
 86     e = 0;
 87     src = 0;
 88     des = 2 * size + 1;
 89     V = des;
 90     memset(first, -1, sizeof(first));
 91     for (i = 1; i <= size; i++) {
 92         addEdge(getIndex(i), getIndex(i) + 1, 1, 0);
 93     }
 94     for (i = 0; i < (int) arr[1].size(); i++) {
 95         addEdge(src, getIndex(pos[1][i]), 1, -arr[1][i]);
 96     }
 97     for (i = 1; i < n; i++) {
 98         for (j = 0; j < (int) arr[i].size(); j++) {
 99             addEdge(getIndex(pos[i][j]) + 1, getIndex(pos[i + 1][j]), 1,
100                     -arr[i + 1][j]);
101             addEdge(getIndex(pos[i][j]) + 1, getIndex(pos[i + 1][j + 1]), 1,
102                     -arr[i + 1][j + 1]);
103         }
104     }
105     for (j = 0; j < (int) arr[n].size(); j++) {
106         addEdge(getIndex(pos[n][j]) + 1, des, 1, 0);
107     }
108     printf("%d\n", -MinCostMaxFlow());
109 }
110 void rule2() {
111     int i, j;
112     e = 0;
113     src = 0;
114     des = size + 1;
115     V = des;
116     memset(first, -1, sizeof(first));
117     for (i = 0; i < (int) arr[1].size(); i++) {
118         addEdge(src, pos[1][i], 1, -arr[1][i]);
119     }
120     for (i = 1; i < n; i++) {
121         for (j = 0; j < (int) arr[i].size(); j++) {
122             addEdge(pos[i][j], pos[i + 1][j], 1, -arr[i + 1][j]);
123             addEdge(pos[i][j], pos[i + 1][j + 1], 1, -arr[i + 1][j + 1]);
124         }
125     }
126     for (j = 0; j < (int) arr[n].size(); j++) {
127         addEdge(pos[n][j], des, oo, 0);
128     }
129     printf("%d\n", -MinCostMaxFlow());
130 }
131 void rule3() {
132     int i, j;
133     e = 0;
134     src = 0;
135     des = size + 1;
136     V = des;
137     memset(first, -1, sizeof(first));
138     for (i = 0; i < (int) arr[1].size(); i++) {
139         addEdge(src, pos[1][i], 1, -arr[1][i]);
140     }
141     for (i = 1; i < n; i++) {
142         for (j = 0; j < (int) arr[i].size(); j++) {
143             addEdge(pos[i][j], pos[i + 1][j], oo, -arr[i + 1][j]);
144             addEdge(pos[i][j], pos[i + 1][j + 1], oo, -arr[i + 1][j + 1]);
145         }
146     }
147     for (j = 0; j < (int) arr[n].size(); j++) {
148         addEdge(pos[n][j], des, oo, 0);
149     }
150     printf("%d\n", -MinCostMaxFlow());
151 }
152 int main() {
153     int i, j;
154     int tmp;
155     while (~scanf("%d%d", &m, &n)) {
156         size = 0;
157         for (i = 1; i <= n; i++) {
158             arr[i].clear();
159             pos[i].clear();
160             for (j = 0; j < m + i - 1; j++) {
161                 scanf("%d", &tmp);
162                 arr[i].push_back(tmp);
163                 pos[i].push_back(++size);
164             }
165         }
166         rule1();
167         rule2();
168         rule3();
169     }
170     return 0;
171 }

（17）运输问题：网络费用流量。

思路：

1。最小费用最大流。

2。最大费用最大流，费用乘以-1，求最小费用最大流。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<vector>
  5 #define oo 0x7FFFFFFF
  6 #define MAXL 1010
  7 #define MAXN 10010
  8 #define MAXM 1000010
  9 using namespace std;
 10 int V, n, m, e;
 11 int src, des;
 12 int link[MAXN], father[MAXN];
 13 int first[MAXN], cost[MAXM], flow[MAXM], next[MAXM], v[MAXM];
 14 int dis[MAXN];
 15 bool inq[MAXN];
 16 
 17 int a[MAXN];
 18 int b[MAXN];
 19 int c[MAXL][MAXL];
 20 void addEdge(int x, int y, int f, int c) {
 21     v[e] = y;
 22     flow[e] = f;
 23     cost[e] = c;
 24     next[e] = first[x];
 25     first[x] = e++;
 26 
 27     v[e] = x;
 28     flow[e] = 0;
 29     cost[e] = -c;
 30     next[e] = first[y];
 31     first[y] = e++;
 32 }
 33 bool SPFA() {
 34     int i, u;
 35     deque<int> q;
 36     memset(inq, false, sizeof(inq));
 37     for (i = 0; i <= V; i++) {
 38         dis[i] = oo;
 39     }
 40     dis[src] = 0;
 41     q.push_back(src);
 42     inq[src] = true;
 43     while (!q.empty()) {
 44         u = q.front();
 45         q.pop_front();
 46         inq[u] = false;
 47         for (i = first[u]; i != -1; i = next[i]) {
 48             if (flow[i] && dis[v[i]] > dis[u] + cost[i]) {
 49                 dis[v[i]] = dis[u] + cost[i];
 50                 father[v[i]] = u;
 51                 link[v[i]] = i;
 52                 if (!inq[v[i]]) {
 53                     inq[v[i]] = true;
 54                     if (!q.empty() && dis[v[i]] <= dis[q.front()]) {
 55                         q.push_front(v[i]);
 56                     } else {
 57                         q.push_back(v[i]);
 58                     }
 59                 }
 60             }
 61         }
 62     }
 63     return dis[des] != oo;
 64 }
 65 int MinCostMaxFlow() {
 66     int u;
 67     int ans;
 68     int tmp;
 69     for (ans = 0; SPFA();) {
 70         tmp = oo;
 71         for (u = des; u; u = father[u]) {
 72             tmp = min(tmp, flow[link[u]]);
 73         }
 74         for (u = des; u; u = father[u]) {
 75             flow[link[u]] -= tmp;
 76             flow[link[u] ^ 1] += tmp;
 77         }
 78         ans += tmp * dis[des];
 79     }
 80     return ans;
 81 }
 82 void calMinCostMaxFlow(int flag) {
 83     int i, j;
 84     src = 0;
 85     des = n + m + 1;
 86     V = des;
 87     e = 0;
 88     memset(first, -1, sizeof(first));
 89     for (i = 1; i <= m; i++) {
 90         addEdge(src, i, a[i], 0);
 91     }
 92     for (i = 1; i <= n; i++) {
 93         addEdge(m + i, des, b[i], 0);
 94     }
 95     for (i = 1; i <= m; i++) {
 96         for (j = 1; j <= n; j++) {
 97             addEdge(i, m + j, oo, c[i][j] * flag);
 98         }
 99     }
100     printf("%d\n", flag * MinCostMaxFlow());
101 }
102 int main() {
103     int i, j;
104     while (~scanf("%d%d", &m, &n)) {
105         for (i = 1; i <= m; i++) {
106             scanf("%d", &a[i]);
107         }
108         for (i = 1; i <= n; i++) {
109             scanf("%d", &b[i]);
110         }
111         for (i = 1; i <= m; i++) {
112             for (j = 1; j <= n; j++) {
113                 scanf("%d", &c[i][j]);
114             }
115         }
116         calMinCostMaxFlow(1);
117         calMinCostMaxFlow(-1);
118     }
119     return 0;
120 }

（18）分配问题：二分图最佳匹配。

思路：

同（17）运输问题。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<vector>
  5 #define oo 0x7FFFFFFF
  6 #define MAXL 1010
  7 #define MAXN 10010
  8 #define MAXM 1000010
  9 using namespace std;
 10 int V, n, e;
 11 int src, des;
 12 int link[MAXN], father[MAXN];
 13 int first[MAXN], cost[MAXM], flow[MAXM], next[MAXM], v[MAXM];
 14 int dis[MAXN];
 15 bool inq[MAXN];
 16 
 17 int c[MAXL][MAXL];
 18 void addEdge(int x, int y, int f, int c) {
 19     v[e] = y;
 20     flow[e] = f;
 21     cost[e] = c;
 22     next[e] = first[x];
 23     first[x] = e++;
 24 
 25     v[e] = x;
 26     flow[e] = 0;
 27     cost[e] = -c;
 28     next[e] = first[y];
 29     first[y] = e++;
 30 }
 31 bool SPFA() {
 32     int i, u;
 33     deque<int> q;
 34     memset(inq, false, sizeof(inq));
 35     for (i = 0; i <= V; i++) {
 36         dis[i] = oo;
 37     }
 38     dis[src] = 0;
 39     q.push_back(src);
 40     inq[src] = true;
 41     while (!q.empty()) {
 42         u = q.front();
 43         q.pop_front();
 44         inq[u] = false;
 45         for (i = first[u]; i != -1; i = next[i]) {
 46             if (flow[i] && dis[v[i]] > dis[u] + cost[i]) {
 47                 dis[v[i]] = dis[u] + cost[i];
 48                 father[v[i]] = u;
 49                 link[v[i]] = i;
 50                 if (!inq[v[i]]) {
 51                     inq[v[i]] = true;
 52                     if (!q.empty() && dis[v[i]] <= dis[q.front()]) {
 53                         q.push_front(v[i]);
 54                     } else {
 55                         q.push_back(v[i]);
 56                     }
 57                 }
 58             }
 59         }
 60     }
 61     return dis[des] != oo;
 62 }
 63 int MinCostMaxFlow() {
 64     int u;
 65     int ans;
 66     int tmp;
 67     for (ans = 0; SPFA();) {
 68         tmp = oo;
 69         for (u = des; u; u = father[u]) {
 70             tmp = min(tmp, flow[link[u]]);
 71         }
 72         for (u = des; u; u = father[u]) {
 73             flow[link[u]] -= tmp;
 74             flow[link[u] ^ 1] += tmp;
 75         }
 76         ans += tmp * dis[des];
 77     }
 78     return ans;
 79 }
 80 void calMinCostMaxFlow(int flag) {
 81     int i, j;
 82     src = 0;
 83     des = n + n + 1;
 84     V = des;
 85     e = 0;
 86     memset(first, -1, sizeof(first));
 87     for (i = 1; i <= n; i++) {
 88         for (j = 1; j <= n; j++) {
 89             addEdge(i, n + j, oo, c[i][j] * flag);
 90         }
 91     }
 92     for (i = 1; i <= n; i++) {
 93         addEdge(src, i, 1, 0);
 94         addEdge(n + i, des, 1, 0);
 95     }
 96     printf("%d\n", flag * MinCostMaxFlow());
 97 }
 98 int main() {
 99     int i, j;
100     while (~scanf("%d", &n)) {
101         for (i = 1; i <= n; i++) {
102             for (j = 1; j <= n; j++) {
103                 scanf("%d", &c[i][j]);
104             }
105         }
106         calMinCostMaxFlow(1);
107         calMinCostMaxFlow(-1);
108     }
109     return 0;
110 }

（19）负载平衡问题：最小代价供求。

思路：

1。向相邻的左右两个点连边，流量为oo，费用为1。

2。若一个点库存比平均值多a，则从源向该点连边，流量为a，费用为0。

3。若一个点库存比平均值少a，则从该点向汇连边，流量为a，费用为0。

4。求最小费用最大流。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #define oo 123456
  5 #define MAXN 100010
  6 #define MAXM 1000010
  7 using namespace std;
  8 int V, n, m, e;
  9 int src, des;
 10 int lk[MAXN], father[MAXN];
 11 int first[MAXN], cost[MAXM], flow[MAXM], next[MAXM], v[MAXM];
 12 int dis[MAXN];
 13 bool inq[MAXN];
 14 
 15 int arr[MAXN];
 16 void addEdge(int x, int y, int f, int c) {
 17     v[e] = y;
 18     flow[e] = f;
 19     cost[e] = c;
 20     next[e] = first[x];
 21     first[x] = e++;
 22 
 23     v[e] = x;
 24     flow[e] = 0;
 25     cost[e] = -c;
 26     next[e] = first[y];
 27     first[y] = e++;
 28 }
 29 bool SPFA() {
 30     int i, u;
 31     deque<int> q;
 32     memset(inq, false, sizeof(inq));
 33     for (i = 0; i <= V; i++) {
 34         dis[i] = oo;
 35     }
 36     dis[src] = 0;
 37     q.push_back(src);
 38     inq[src] = true;
 39     while (!q.empty()) {
 40         u = q.front();
 41         q.pop_front();
 42         inq[u] = false;
 43         for (i = first[u]; i != -1; i = next[i]) {
 44             if (flow[i] && dis[v[i]] > dis[u] + cost[i]) {
 45                 dis[v[i]] = dis[u] + cost[i];
 46                 father[v[i]] = u;
 47                 lk[v[i]] = i;
 48                 if (!inq[v[i]]) {
 49                     inq[v[i]] = true;
 50                     if (!q.empty() && dis[v[i]] <= dis[q.front()]) {
 51                         q.push_front(v[i]);
 52                     } else {
 53                         q.push_back(v[i]);
 54                     }
 55                 }
 56             }
 57         }
 58     }
 59     return dis[des] != oo;
 60 }
 61 int MinCostMaxFlow() {
 62     int u;
 63     int ans;
 64     int tmp;
 65     for (ans = 0; SPFA();) {
 66         tmp = oo;
 67         for (u = des; u; u = father[u]) {
 68             tmp = min(tmp, flow[lk[u]]);
 69         }
 70         for (u = des; u; u = father[u]) {
 71             flow[lk[u]] -= tmp;
 72             flow[lk[u] ^ 1] += tmp;
 73         }
 74         ans += tmp * dis[des];
 75     }
 76     return ans;
 77 }
 78 int main() {
 79     int i, j;
 80     int sum;
 81     while (~scanf("%d", &n)) {
 82         e = 0;
 83         src = 0;
 84         des = n + 1;
 85         V = des;
 86         memset(first, -1, sizeof(first));
 87         sum = 0;
 88         for (i = 1; i <= n; i++) {
 89             scanf("%d", &arr[i]);
 90             sum += arr[i];
 91         }
 92         sum /= n;
 93         for (i = 1; i <= n; i++) {
 94             arr[i] -= sum;
 95             if (arr[i] > 0) {
 96                 addEdge(src, i, arr[i], 0);
 97             } else if (arr[i] < 0) {
 98                 addEdge(i, des, -arr[i], 0);
 99             }
100             j = i + 1;
101             if (j > n) {
102                 j = 1;
103             }
104             addEdge(i, j, oo, 1);
105             addEdge(j, i, oo, 1);
106             j = i - 1;
107             if (j < 1) {
108                 j = n;
109             }
110             addEdge(i, j, oo, 1);
111             addEdge(j, i, oo, 1);
112         }
113         printf("%d\n", MinCostMaxFlow());
114     }
115     return 0;
116 }

（20）深海机器人问题：线性规划网络优化。

思路：

1。每个权值只能取一次，流量设为1。

2。每条路径可以取多次，流量设为oo。

3。最大费用最大流。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #define oo 123456
  5 #define MAXN 100010
  6 #define MAXM 1000010
  7 using namespace std;
  8 int V, n, m, e;
  9 int src, des;
 10 int lk[MAXN], father[MAXN];
 11 int first[MAXN], cost[MAXM], flow[MAXM], next[MAXM], v[MAXM];
 12 int dis[MAXN];
 13 bool inq[MAXN];
 14 
 15 void addEdge(int x, int y, int f, int c) {
 16     v[e] = y;
 17     flow[e] = f;
 18     cost[e] = c;
 19     next[e] = first[x];
 20     first[x] = e++;
 21 
 22     v[e] = x;
 23     flow[e] = 0;
 24     cost[e] = -c;
 25     next[e] = first[y];
 26     first[y] = e++;
 27 }
 28 bool SPFA() {
 29     int i, u;
 30     deque<int> q;
 31     memset(inq, false, sizeof(inq));
 32     for (i = 0; i <= V; i++) {
 33         dis[i] = oo;
 34     }
 35     dis[src] = 0;
 36     q.push_back(src);
 37     inq[src] = true;
 38     while (!q.empty()) {
 39         u = q.front();
 40         q.pop_front();
 41         inq[u] = false;
 42         for (i = first[u]; i != -1; i = next[i]) {
 43             if (flow[i] && dis[v[i]] > dis[u] + cost[i]) {
 44                 dis[v[i]] = dis[u] + cost[i];
 45                 father[v[i]] = u;
 46                 lk[v[i]] = i;
 47                 if (!inq[v[i]]) {
 48                     inq[v[i]] = true;
 49                     if (!q.empty() && dis[v[i]] <= dis[q.front()]) {
 50                         q.push_front(v[i]);
 51                     } else {
 52                         q.push_back(v[i]);
 53                     }
 54                 }
 55             }
 56         }
 57     }
 58     return dis[des] != oo;
 59 }
 60 int MinCostMaxFlow() {
 61     int u;
 62     int ans;
 63     int tmp;
 64     for (ans = 0; SPFA();) {
 65         tmp = oo;
 66         for (u = des; u; u = father[u]) {
 67             tmp = min(tmp, flow[lk[u]]);
 68         }
 69         for (u = des; u; u = father[u]) {
 70             flow[lk[u]] -= tmp;
 71             flow[lk[u] ^ 1] += tmp;
 72         }
 73         ans += tmp * dis[des];
 74     }
 75     return ans;
 76 }
 77 int main() {
 78     int a, b;
 79     int p, q;
 80     int i, j;
 81     int x, y, val;
 82     while (~scanf("%d%d%d%d", &a, &b, &p, &q)) {
 83         e = 0;
 84         src = 0;
 85         des = (p + 1) * (q + 1) + 1;
 86         V = des;
 87         memset(first, -1, sizeof(first));
 88         for (i = 0; i <= p; i++) {
 89             for (j = 1; j <= q; j++) {
 90                 scanf("%d", &x);
 91                 addEdge(i * (q + 1) + j, i * (q + 1) + j + 1, 1, -x);
 92                 addEdge(i * (q + 1) + j, i * (q + 1) + j + 1, oo, 0);
 93             }
 94         }
 95         for (i = 0; i <= q; i++) {
 96             for (j = 1; j <= p; j++) {
 97                 scanf("%d", &x);
 98                 addEdge((j - 1) * (q + 1) + i + 1, j * (q + 1) + i + 1, 1, -x);
 99                 addEdge((j - 1) * (q + 1) + i + 1, j * (q + 1) + i + 1, oo, 0);
100             }
101         }
102         while (a--) {
103             scanf("%d%d%d", &val, &y, &x);
104             addEdge(src, y * (q + 1) + x + 1, val, 0);
105         }
106         while (b--) {
107             scanf("%d%d%d", &val, &y, &x);
108             addEdge(y * (q + 1) + x + 1, des, val, 0);
109         }
110         printf("%d\n", -MinCostMaxFlow());
111     }
112 }

（21）最长k可重区间集问题：最大权不相交路径。

思路：

1。对所有端点排序后，离散化。

2。源到1，流量为k，费用为0。最后一个点到汇，流量为oo，费用为0。

3。若有区间[x,y]，则x向y连边，流量为1，费用为x-y。

4。最大费用最大流。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<algorithm>
  5 #define oo 123456
  6 #define MAXN 100010
  7 #define MAXM 1000010
  8 using namespace std;
  9 int V, n, m, e;
 10 int src, des;
 11 int lk[MAXN], father[MAXN];
 12 int first[MAXN], cost[MAXM], flow[MAXM], next[MAXM], v[MAXM];
 13 int dis[MAXN];
 14 bool inq[MAXN];
 15 
 16 int arr[MAXN];
 17 int size;
 18 struct point {
 19     int x, y;
 20 } p[MAXN];
 21 void addEdge(int x, int y, int f, int c) {
 22     v[e] = y;
 23     flow[e] = f;
 24     cost[e] = c;
 25     next[e] = first[x];
 26     first[x] = e++;
 27 
 28     v[e] = x;
 29     flow[e] = 0;
 30     cost[e] = -c;
 31     next[e] = first[y];
 32     first[y] = e++;
 33 }
 34 bool SPFA() {
 35     int i, u;
 36     deque<int> q;
 37     memset(inq, false, sizeof(inq));
 38     for (i = 0; i <= V; i++) {
 39         dis[i] = oo;
 40     }
 41     dis[src] = 0;
 42     q.push_back(src);
 43     inq[src] = true;
 44     while (!q.empty()) {
 45         u = q.front();
 46         q.pop_front();
 47         inq[u] = false;
 48         for (i = first[u]; i != -1; i = next[i]) {
 49             if (flow[i] && dis[v[i]] > dis[u] + cost[i]) {
 50                 dis[v[i]] = dis[u] + cost[i];
 51                 father[v[i]] = u;
 52                 lk[v[i]] = i;
 53                 if (!inq[v[i]]) {
 54                     inq[v[i]] = true;
 55                     if (!q.empty() && dis[v[i]] <= dis[q.front()]) {
 56                         q.push_front(v[i]);
 57                     } else {
 58                         q.push_back(v[i]);
 59                     }
 60                 }
 61             }
 62         }
 63     }
 64     return dis[des] != oo;
 65 }
 66 int MinCostMaxFlow() {
 67     int u;
 68     int ans;
 69     int tmp;
 70     for (ans = 0; SPFA();) {
 71         tmp = oo;
 72         for (u = des; u; u = father[u]) {
 73             tmp = min(tmp, flow[lk[u]]);
 74         }
 75         for (u = des; u; u = father[u]) {
 76             flow[lk[u]] -= tmp;
 77             flow[lk[u] ^ 1] += tmp;
 78         }
 79         ans += tmp * dis[des];
 80     }
 81     return ans;
 82 }
 83 int main() {
 84     int i;
 85     int m;
 86     int x, y;
 87     while (~scanf("%d%d", &n, &m)) {
 88         e = 0;
 89         src = 0;
 90         des = n + n + 1;
 91         V = des;
 92         memset(first, -1, sizeof(first));
 93         size = 0;
 94         for (i = 0; i < n; i++) {
 95             scanf("%d%d", &p[i].x, &p[i].y);
 96             arr[size++] = p[i].x;
 97             arr[size++] = p[i].y;
 98         }
 99         sort(arr, arr + size);
100         size = unique(arr, arr + size) - arr;
101         addEdge(src, 1, m, 0);
102         addEdge(size, des, oo, 0);
103         for (i = 2; i <= size; i++) {
104             addEdge(i - 1, i, oo, 0);
105         }
106         for (i = 0; i < n; i++) {
107             x = lower_bound(arr, arr + size, p[i].x) - arr + 1;
108             y = lower_bound(arr, arr + size, p[i].y) - arr + 1;
109             addEdge(x, y, 1, p[i].x - p[i].y);
110         }
111         printf("%d\n", -MinCostMaxFlow());
112     }
113     return 0;
114 }

（24）骑士共存问题：二分图最大独立集。

思路：

1。冲突的位置相互连边。

2.。添加源，汇。

3。求最大流。

View Code

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<vector>
  4 #define MAXL 210
  5 #define MAXN 100010
  6 #define MAXM 1000010
  7 #define oo 0x7FFFFFFF
  8 using namespace std;
  9 int first[MAXN], next[MAXM], v[MAXM], cost[MAXM], e;
 10 int n;
 11 int src, des;
 12 bool flag[MAXL][MAXL];
 13 int go[][2] = { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 },
 14         { -2, 1 }, { -2, -1 } };
 15 inline void addEdge(int x, int y, int val) {
 16     v[e] = y;
 17     cost[e] = val;
 18     next[e] = first[x];
 19     first[x] = e++;
 20 
 21     v[e] = x;
 22     cost[e] = 0;
 23     next[e] = first[y];
 24     first[y] = e++;
 25 }
 26 int SAP() {
 27     int pre[MAXN], cur[MAXN], dis[MAXN], gap[MAXN];
 28     int flow = 0;
 29     int aug = oo;
 30     int x, y;
 31     bool flag;
 32     for (int i = 0; i < n; i++) {
 33         cur[i] = first[i];
 34         gap[i] = dis[i] = 0;
 35     }
 36     gap[src] = n;
 37     x = pre[src] = src;
 38     while (dis[src] < n) {
 39         flag = false;
 40         for (int &j = cur[x]; j != -1; j = next[j]) {
 41             y = v[j];
 42             if (cost[j] > 0 && dis[x] == dis[y] + 1) {
 43                 flag = true;
 44                 aug = min(aug, cost[j]);
 45                 pre[y] = x;
 46                 x = y;
 47                 if (x == des) {
 48                     flow += aug;
 49                     while (x != src) {
 50                         x = pre[x];
 51                         cost[cur[x]] -= aug;
 52                         cost[cur[x] ^ 1] += aug;
 53                     }
 54                     aug = oo;
 55                 }
 56                 break;
 57             }
 58         }
 59         if (flag) {
 60             continue;
 61         }
 62         int tmp = n;
 63         for (int j = first[x]; j != -1; j = next[j]) {
 64             y = v[j];
 65             if (cost[j] > 0 && dis[y] < tmp) {
 66                 tmp = dis[y];
 67                 cur[x] = j;
 68             }
 69         }
 70         if ((--gap[dis[x]]) == 0) {
 71             break;
 72         }
 73         gap[dis[x] = tmp + 1]++;
 74         x = pre[x];
 75     }
 76     return flow;
 77 }
 78 int getIndex(int x, int y) {
 79     return (x - 1) * n + y;
 80 }
 81 int main() {
 82     int m;
 83     int i, j, k;
 84     int x, y;
 85     int ans;
 86     while (~scanf("%d%d", &n, &m)) {
 87         src = 0;
 88         des = 2 * n * n + 1;
 89         e = 0;
 90         memset(first, -1, sizeof(first));
 91         memset(flag, false, sizeof(flag));
 92         for (i = 0; i < m; i++) {
 93             scanf("%d%d", &x, &y);
 94             flag[x][y] = true;
 95         }
 96         for (i = 1; i <= n; i++) {
 97             for (j = 1; j <= n; j++) {
 98                 if (flag[i][j]) {
 99                     continue;
100                 }
101                 addEdge(src, getIndex(i, j), 1);
102                 addEdge(n * n + getIndex(i, j), des, 1);
103                 for (k = 0; k < 8; k++) {
104                     x = i + go[k][0];
105                     y = j + go[k][1];
106                     if (x > 0 && x <= n && y > 0 && y <= n && !flag[x][y]) {
107                         addEdge(getIndex(i, j), n * n + getIndex(x, y), 1);
108                     }
109                 }
110             }
111         }
112         ans = n * n - m;
113         n = des + 1;
114         printf("%d\n", ans - SAP() / 2);
115     }
116     return 0;
117 }

新博客：www.zhixiangli.com