（1）飞行员配对方案问题：二分图最大匹配。
思路：略。
View Code 1 #include2 #include 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 #include2 #include 3 #include 4 #include 5 #include 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 g[MAXL]; 19 vector test; 20 vector 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 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 #include2 #include 3 #include 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 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 #include2 #include 3 #include 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 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 #include2 #include 3 #include 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 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 #include2 #include 3 #include 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 #include2 #include 3 #include 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 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 #include2 #include 3 #include 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 #include2 #include 3 #include 4 #include 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 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 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include
（12）软件补丁问题：最小转移代价。
思路：
1。只有20个补丁，很容易想到状态压缩。
2。最多(1<<20)个状态，一个状态到另一个状态间有一个花费。
3。求最短花费，就是最短路了。
题目描述有错：第二个字符串中'-'是f1的，'+'是f2的。
View Code 1 #include2 #include 3 #include 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 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 #include2 #include 3 #include 4 #include 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 path[MAXN]; 14 vector cap; 15 vector ind[MAXN]; 16 vector 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 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 #include2 #include 3 #include 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 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 <= m52 && 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 #include2 #include 3 #include 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 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 #include2 #include 3 #include 4 #include 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 arr[MAXN]; 17 vector 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 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 #include2 #include 3 #include 4 #include 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 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 #include2 #include 3 #include 4 #include 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 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 #include2 #include 3 #include 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 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 #include2 #include 3 #include 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 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 #include2 #include 3 #include 4 #include 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 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 #include2 #include 3 #include 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 }