线性规划与网络流24题

分类: IT文章 • 2025-02-04 12:28:25

诈个尸。

二分图匹配。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 using namespace std;
  7 const int INF = 1e9;
  8 const int maxn = 2e5 + 10;
  9 int lv[maxn], it[maxn];
 10 int cnt, h[maxn];
 11 
 12 struct edge
 13 {
 14     int to, pre, cap;
 15 } e[maxn<<1];
 16 
 17 void init()
 18 {
 19     memset(h, -1, sizeof(h));
 20     cnt = 0;
 21 }
 22 
 23 void add(int from, int to, int cap)
 24 {
 25     e[cnt].pre = h[from];
 26     e[cnt].to = to;
 27     e[cnt].cap = cap;
 28     h[from] = cnt;
 29     cnt++;
 30 }
 31 
 32 void ad(int from, int to, int cap)
 33 {
 34     add(from, to, cap);
 35     add(to, from, 0);
 36 }
 37 
 38 void bfs(int s)
 39 {
 40     memset(lv, -1, sizeof(lv));
 41     queue<int> q;
 42     lv[s] = 0;
 43     q.push(s);
 44     while(!q.empty())
 45     {
 46         int v = q.front(); q.pop();
 47         for(int i = h[v]; i >= 0; i = e[i].pre)
 48         {
 49             int cap = e[i].cap, to = e[i].to;
 50             if(cap > 0 && lv[to] < 0)
 51             {
 52                 lv[to] = lv[v] + 1;
 53                 q.push(to);
 54             }
 55         }
 56     }
 57 }
 58 
 59 int dfs(int v, int t, int f)
 60 {
 61     if(v == t) return f;
 62     for(int &i = it[v]; i >= 0; i = e[i].pre)
 63     {
 64         int &cap = e[i].cap, to = e[i].to;
 65         if(cap > 0 && lv[v] < lv[to])
 66         {
 67             int d = dfs(to, t, min(f, cap));
 68             if(d > 0)
 69             {
 70                 cap -= d;
 71                 e[i^1].cap += d;
 72                 return d;
 73             }
 74         }
 75     }
 76     return 0;
 77 }
 78 
 79 int Dinic(int s, int t)
 80 {
 81     int flow = 0;
 82     while(1)
 83     {
 84         bfs(s);
 85         if(lv[t] < 0) return flow;
 86         memcpy(it, h, sizeof(it));
 87         int f;
 88         while((f = dfs(s, t, INF)) > 0) flow += f;
 89     }
 90 }
 91 
 92 int main(void)
 93 {
 94     init();
 95     int m, n;
 96     scanf("%d %d", &m, &n);
 97     while(1)
 98     {
 99         int u, v;
100         scanf("%d %d", &u, &v);
101         if(u == -1) break;
102         ad(u, v, 1);
103     }
104     int S = n + 1, T = S + 1;
105     for(int i = 1; i <= m; i++) ad(S, i, 1);
106     for(int i = m + 1; i <= n; i++) ad(i, T, 1);
107     int ans = Dinic(S, T);
108     if(!ans) puts("No Solution!");
109     else
110     {
111         printf("%d
", ans);
112         for(int i = 1; i <= m; i++)
113             for(int j = h[i]; j != -1; j = e[j].pre)
114                 if(e[j].to <= n && !e[j].cap) printf("%d %d
", i, e[j].to);
115     }
116     return 0;
117 }

Aguin

2.太空飞行计划问题

最大权闭合图转最大流。

见《最小割模型在信息学竞赛中的应用》。

同时注意割边必满流，满流不一定是割边。

但是Dinic找割点是很方便的，看lv就好。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 #include <vector>
  7 using namespace std;
  8 const int INF = 1e9;
  9 const int maxn = 2e5 + 10;
 10 int lv[maxn], it[maxn];
 11 int cnt, h[maxn];
 12 vector<int> E, I;
 13 
 14 struct edge
 15 {
 16     int to, pre, cap;
 17 } e[maxn<<1];
 18 
 19 void init()
 20 {
 21     memset(h, -1, sizeof(h));
 22     cnt = 0;
 23 }
 24 
 25 void add(int from, int to, int cap)
 26 {
 27     e[cnt].pre = h[from];
 28     e[cnt].to = to;
 29     e[cnt].cap = cap;
 30     h[from] = cnt;
 31     cnt++;
 32 }
 33 
 34 void ad(int from, int to, int cap)
 35 {
 36     add(from, to, cap);
 37     add(to, from, 0);
 38 }
 39 
 40 void bfs(int s)
 41 {
 42     memset(lv, -1, sizeof(lv));
 43     queue<int> q;
 44     lv[s] = 0;
 45     q.push(s);
 46     while(!q.empty())
 47     {
 48         int v = q.front(); q.pop();
 49         for(int i = h[v]; i >= 0; i = e[i].pre)
 50         {
 51             int cap = e[i].cap, to = e[i].to;
 52             if(cap > 0 && lv[to] < 0)
 53             {
 54                 lv[to] = lv[v] + 1;
 55                 q.push(to);
 56             }
 57         }
 58     }
 59 }
 60 
 61 int dfs(int v, int t, int f)
 62 {
 63     if(v == t) return f;
 64     for(int &i = it[v]; i >= 0; i = e[i].pre)
 65     {
 66         int &cap = e[i].cap, to = e[i].to;
 67         if(cap > 0 && lv[v] < lv[to])
 68         {
 69             int d = dfs(to, t, min(f, cap));
 70             if(d > 0)
 71             {
 72                 cap -= d;
 73                 e[i^1].cap += d;
 74                 return d;
 75             }
 76         }
 77     }
 78     return 0;
 79 }
 80 
 81 int Dinic(int s, int t)
 82 {
 83     int flow = 0;
 84     while(1)
 85     {
 86         bfs(s);
 87         if(lv[t] < 0) return flow;
 88         memcpy(it, h, sizeof(it));
 89         int f;
 90         while((f = dfs(s, t, INF)) > 0) flow += f;
 91     }
 92 }
 93 
 94 int main(void)
 95 {
 96     init();
 97     int m, n, tot = 0;
 98     scanf("%d %d", &m, &n);
 99     int S = m + n + 1, T = S + 1;
100     for(int i = 1; i <= m; i++)
101     {
102         int p, x;
103         scanf("%d", &p);
104         tot += p;
105         ad(S, i, p);
106         while(getchar() == ' ')
107         {
108             scanf("%d", &x);
109             ad(i, x + m, INF);
110         }
111     }
112     for(int i = 1; i <= n; i++)
113     {
114         int c;
115         scanf("%d", &c);
116         ad(i + m, T, c);
117     }
118     int ans = tot - Dinic(S, T);
119     for(int i = 1; i <= m; i++) if(lv[i] != -1) printf("%d ", i); puts("");
120     for(int i = 1; i <= n; i++) if(lv[i+m] != -1) printf("%d ", i); puts("");
121     printf("%d
", ans);
122     return 0;
123 }

Aguin

3.最小路径覆盖问题

DAG上最小路径覆盖转二分图匹配。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 using namespace std;
  7 const int INF = 1e9;
  8 const int maxn = 2e5 + 10;
  9 int lv[maxn], it[maxn];
 10 int cnt, h[maxn];
 11 int n, m;
 12 
 13 struct edge
 14 {
 15     int to, pre, cap;
 16 } e[maxn<<1];
 17 
 18 void init()
 19 {
 20     memset(h, -1, sizeof(h));
 21     cnt = 0;
 22 }
 23 
 24 void add(int from, int to, int cap)
 25 {
 26     e[cnt].pre = h[from];
 27     e[cnt].to = to;
 28     e[cnt].cap = cap;
 29     h[from] = cnt;
 30     cnt++;
 31 }
 32 
 33 void ad(int from, int to, int cap)
 34 {
 35     add(from, to, cap);
 36     add(to, from, 0);
 37 }
 38 
 39 void bfs(int s)
 40 {
 41     memset(lv, -1, sizeof(lv));
 42     queue<int> q;
 43     lv[s] = 0;
 44     q.push(s);
 45     while(!q.empty())
 46     {
 47         int v = q.front(); q.pop();
 48         for(int i = h[v]; i >= 0; i = e[i].pre)
 49         {
 50             int cap = e[i].cap, to = e[i].to;
 51             if(cap > 0 && lv[to] < 0)
 52             {
 53                 lv[to] = lv[v] + 1;
 54                 q.push(to);
 55             }
 56         }
 57     }
 58 }
 59 
 60 int dfs(int v, int t, int f)
 61 {
 62     if(v == t) return f;
 63     for(int &i = it[v]; i >= 0; i = e[i].pre)
 64     {
 65         int &cap = e[i].cap, to = e[i].to;
 66         if(cap > 0 && lv[v] < lv[to])
 67         {
 68             int d = dfs(to, t, min(f, cap));
 69             if(d > 0)
 70             {
 71                 cap -= d;
 72                 e[i^1].cap += d;
 73                 return d;
 74             }
 75         }
 76     }
 77     return 0;
 78 }
 79 
 80 int Dinic(int s, int t)
 81 {
 82     int flow = 0;
 83     while(1)
 84     {
 85         bfs(s);
 86         if(lv[t] < 0) return flow;
 87         memcpy(it, h, sizeof(it));
 88         int f;
 89         while((f = dfs(s, t, INF)) > 0) flow += f;
 90     }
 91 }
 92 
 93 void ans_print(int x)
 94 {
 95     printf("%d ", x);
 96     for(int i = h[x]; i >= 0; i = e[i].pre)
 97         if(!e[i].cap && e[i].to <= n + n)
 98             ans_print(e[i].to - n);
 99 }
100 
101 int main(void)
102 {
103     init();
104     scanf("%d %d", &n, &m);
105     int S = n + n + 1, T = S + 1;
106     for(int i = 1; i <= n; i++) ad(S, i, 1), ad(n + i, T, 1);
107     for(int i = 0; i < m; i++)
108     {
109         int u, v;
110         scanf("%d %d", &u, &v);
111         ad(u, v + n, 1);
112     }
113     int ans = n - Dinic(S, T);
114     for(int i = h[T]; i >= 0; i = e[i].pre)
115     {
116         if(e[i].cap) continue;
117         ans_print(e[i].to - n), puts("");
118     }
119     printf("%d
", ans);
120     return 0;
121 }

Aguin

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <vector> 7 using namespace std; 8 const int INF = 1e9; 9 const int maxn = 2e4 + 10; 10 const int maxm = 2e5; 11 const int m = 1e4; 12 int lv[maxn], it[maxn]; 13 int cnt, h[maxn]; 14 vector<int> is; 15 16 struct edge 17 { 18 int to, pre, cap; 19 } e[maxm<<1]; 20 21 void init() 22 { 23 memset(h, -1, sizeof(h)); 24 cnt = 0; 25 } 26 27 void add(int from, int to, int cap) 28 { 29 e[cnt].pre = h[from]; 30 e[cnt].to = to; 31 e[cnt].cap = cap; 32 h[from] = cnt; 33 cnt++; 34 } 35 36 void ad(int from, int to, int cap) 37 { 38 add(from, to, cap); 39 add(to, from, 0); 40 } 41 42 void bfs(int s) 43 { 44 memset(lv, -1, sizeof(lv)); 45 queue<int> q; 46 lv[s] = 0; 47 q.push(s); 48 while(!q.empty()) 49 { 50 int v = q.front(); q.pop(); 51 for(int i = h[v]; i >= 0; i = e[i].pre) 52 { 53 int cap = e[i].cap, to = e[i].to; 54 if(cap > 0 && lv[to] < 0) 55 { 56 lv[to] = lv[v] + 1; 57 q.push(to); 58 } 59 } 60 } 61 } 62 63 int dfs(int v, int t, int f) 64 { 65 if(v == t) return f; 66 for(int &i = it[v]; i >= 0; i = e[i].pre) 67 { 68 int &cap = e[i].cap, to = e[i].to; 69 if(cap > 0 && lv[v] < lv[to]) 70 { 71 int d = dfs(to, t, min(f, cap)); 72 if(d > 0) 73 { 74 cap -= d; 75 e[i^1].cap += d; 76 return d; 77 } 78 } 79 } 80 return 0; 81 } 82 83 int Dinic(int s, int t) 84 { 85 int flow = 0; 86 while(1) 87 { 88 bfs(s); 89 if(lv[t] < 0) return flow; 90 memcpy(it, h, sizeof(it)); 91 int f; 92 while((f = dfs(s, t, INF)) > 0) flow += f; 93 } 94 } 95 96 void ans_print(int x) 97 { 98 printf("%d ", x); 99 for(int i = h[x]; i >= 0; i = e[i].pre) 100 if(!e[i].cap && e[i].to <= m + m) 101 ans_print(e[i].to - m); 102 } 103 104 int main(void) 105 { 106 for(int i = 1; i * i < maxn; i++) is.push_back(i * i); 107 init(); 108 int n, ans = 0; 109 scanf("%d", &n); 110 int S = m + m + 1, T = S + 1; 111 for(int i = 1; ; i++) 112 { 113 ad(S, i, 1), ad(i + m, T, 1); 114 for(int j = 0; is[j] < i + i; j++) 115 if(is[j] > i) ad(is[j] - i, i + m, 1); 116 ans += Dinic(S, T); 117 if(i - ans > n) {ans = i - 1; break;} 118 } 119 init(); 120 for(int i = 1; i <= ans; i++) 121 { 122 ad(S, i, 1), ad(i + m, T, 1); 123 for(int j = 0; is[j] < i + i; j++) 124 if(is[j] > i) ad(is[j] - i, i + m, 1); 125 } 126 Dinic(S, T); 127 printf("%d ", ans); 128 for(int i = h[T]; i >= 0; i = e[i].pre) 129 { 130 if(e[i].cap) continue; 131 ans_print(e[i].to - m), puts(""); 132 } 133 return 0; 134 }

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 const int INF = 1e9; 8 const int maxn = 2e5 + 10; 9 int lv[maxn], it[maxn]; 10 int cnt, h[maxn]; 11 12 struct edge 13 { 14 int to, pre, cap; 15 } e[maxn<<1]; 16 17 void init() 18 { 19 memset(h, -1, sizeof(h)); 20 cnt = 0; 21 } 22 23 void add(int from, int to, int cap) 24 { 25 e[cnt].pre = h[from]; 26 e[cnt].to = to; 27 e[cnt].cap = cap; 28 h[from] = cnt; 29 cnt++; 30 } 31 32 void ad(int from, int to, int cap) 33 { 34 add(from, to, cap); 35 add(to, from, 0); 36 } 37 38 void bfs(int s) 39 { 40 memset(lv, -1, sizeof(lv)); 41 queue<int> q; 42 lv[s] = 0; 43 q.push(s); 44 while(!q.empty()) 45 { 46 int v = q.front(); q.pop(); 47 for(int i = h[v]; i >= 0; i = e[i].pre) 48 { 49 int cap = e[i].cap, to = e[i].to; 50 if(cap > 0 && lv[to] < 0) 51 { 52 lv[to] = lv[v] + 1; 53 q.push(to); 54 } 55 } 56 } 57 } 58 59 int dfs(int v, int t, int f) 60 { 61 if(v == t) return f; 62 for(int &i = it[v]; i >= 0; i = e[i].pre) 63 { 64 int &cap = e[i].cap, to = e[i].to; 65 if(cap > 0 && lv[v] < lv[to]) 66 { 67 int d = dfs(to, t, min(f, cap)); 68 if(d > 0) 69 { 70 cap -= d; 71 e[i^1].cap += d; 72 return d; 73 } 74 } 75 } 76 return 0; 77 } 78 79 int Dinic(int s, int t) 80 { 81 int flow = 0; 82 while(1) 83 { 84 bfs(s); 85 if(lv[t] < 0) return flow; 86 memcpy(it, h, sizeof(it)); 87 int f; 88 while((f = dfs(s, t, INF)) > 0) flow += f; 89 } 90 } 91 92 int main(void) 93 { 94 int N, M; 95 scanf("%d %d", &N, &M); 96 init(); 97 int sum = 0; 98 int S = N + M + 1, T = S + 1; 99 for(int i = 1; i <= N; i++) 100 { 101 int cap; 102 scanf("%d", &cap); 103 sum += cap; 104 ad(S, i, cap); 105 } 106 for(int i = 1; i <= M; i++) 107 { 108 int cap; 109 scanf("%d", &cap); 110 ad(i + N, T, cap); 111 } 112 for(int i = 1; i <= N; i++) 113 for(int j = 1; j <= M; j++) 114 ad(i, j + N, 1); 115 if(Dinic(S, T) == sum) 116 { 117 puts("1"); 118 for(int i = 1; i <= N; i++) 119 { 120 int fst = 1; 121 for(int j = h[i]; j >= 0; j = e[j].pre) 122 { 123 if(e[j].to != S && e[j].cap == 0) 124 { 125 if(fst) printf("%d", e[j].to - N); 126 else printf(" %d", e[j].to - N); 127 fst = 0; 128 } 129 } 130 puts(""); 131 } 132 } 133 else puts("0"); 134 return 0; 135 }

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 using namespace std; 7 const int INF = 1e9; 8 const int maxn = 2e5 + 10; 9 int lv[maxn], it[maxn]; 10 int cnt, h[maxn]; 11 12 struct edge 13 { 14 int to, pre, cap; 15 } e[maxn<<1]; 16 17 void init() 18 { 19 memset(h, -1, sizeof(h)); 20 cnt = 0; 21 } 22 23 void add(int from, int to, int cap) 24 { 25 e[cnt].pre = h[from]; 26 e[cnt].to = to; 27 e[cnt].cap = cap; 28 h[from] = cnt; 29 cnt++; 30 } 31 32 void ad(int from, int to, int cap) 33 { 34 add(from, to, cap); 35 add(to, from, 0); 36 } 37 38 void bfs(int s) 39 { 40 memset(lv, -1, sizeof(lv)); 41 queue<int> q; 42 lv[s] = 0; 43 q.push(s); 44 while(!q.empty()) 45 { 46 int v = q.front(); q.pop(); 47 for(int i = h[v]; i >= 0; i = e[i].pre) 48 { 49 int cap = e[i].cap, to = e[i].to; 50 if(cap > 0 && lv[to] < 0) 51 { 52 lv[to] = lv[v] + 1; 53 q.push(to); 54 } 55 } 56 } 57 } 58 59 int dfs(int v, int t, int f) 60 { 61 if(v == t) return f; 62 for(int &i = it[v]; i >= 0; i = e[i].pre) 63 { 64 int &cap = e[i].cap, to = e[i].to; 65 if(cap > 0 && lv[v] < lv[to]) 66 { 67 int d = dfs(to, t, min(f, cap)); 68 if(d > 0) 69 { 70 cap -= d; 71 e[i^1].cap += d; 72 return d; 73 } 74 } 75 } 76 return 0; 77 } 78 79 int Dinic(int s, int t) 80 { 81 int flow = 0; 82 while(1) 83 { 84 bfs(s); 85 if(lv[t] < 0) return flow; 86 memcpy(it, h, sizeof(it)); 87 int f; 88 while((f = dfs(s, t, INF)) > 0) flow += f; 89 } 90 } 91 92 int a[444], dp[444]; 93 int main(void) 94 { 95 int n, s = 0; 96 scanf("%d", &n); 97 int S = 2 * n + 1, T = S + 1; 98 for(int i = 1; i <= n; i++) 99 { 100 scanf("%d", a + i); 101 dp[i] = 1; 102 for(int j = 1; j < i; j++) 103 if(a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1); 104 s = max(s, dp[i]); 105 } 106 107 printf("%d ", s); 108 109 init(); 110 for(int i = 1; i <= n; i++) 111 { 112 ad(i, i + n, 1); 113 114 if(dp[i] == 1) ad(S, i, 1); 115 if(dp[i] == s) ad(i + n, T, 1); 116 117 for(int j = 1; j <= i; j++) 118 if(a[j] < a[i] && dp[j] + 1 == dp[i]) ad(j + n, i, 1); 119 } 120 121 int ans = Dinic(S, T); 122 printf("%d ", ans); 123 124 ad(1, 1 + n, INF); 125 ad(n, n + n, INF); 126 ad(S, 1, INF); 127 if(dp[n] == s) ad(n + n, T, INF); 128 129 printf("%d ", ans + Dinic(S, T)); 130 131 return 0; 132 }

线性规划与网络流24题

相关推荐