首页 > 代码库 > HDU 4106

HDU 4106

有很多种写法,不过基本大同小异

不过记得两年前自己居然写了让自己现在诡异所思的代码

建图一:

最小费用最大流:n个点拆成n-m+1个区间,每两个相邻区间之间连边,权值为0,流量为k

对于每一个点,能包括它的最左边的区间向这个区间无交集的下一个区间连一条边,权值为这个点的负权值,流量为1

大致思想就是样,因为一个区间最多能被切k次,所以切完k次后的每一次流量都要流到跟这个区间完全没有交集的区间去

采用负权值,求出最小费用最大流后费用取反就是答案了

  1 #include <iostream>  2 #include <algorithm>  3 #include <cstdio>  4 #include <cstdlib>  5 #include <cstring>  6 #include <queue>  7 #include <vector>  8 #include <string>  9  10 using namespace std; 11  12 typedef long long LL; 13 typedef pair <int, int> PII; 14  15 const int N = 1e3 + 7; 16 const int M = N * N * 4; 17 const int INF = 0x3f3f3f3f; 18 const int MOD = 1e9 + 7; 19 const double EPS = 1e-12; 20  21 struct edge{ 22     int x, ne, c, f, w; 23 }; 24  25 struct MinCostFlow{ 26     edge e[M]; 27     int S, T, pos, quantity, cost; 28     int head[N << 1], dis[N << 1], pre[N << 1], at[N << 1]; 29     queue <int> q; 30     bool used[N << 1]; 31      32     void adde(int u, int v, int c, int w){ 33         //printf("Add edge : %d -> %d c : %d w : %d\n", u, v, c, w); 34         e[++pos] = (edge){v, head[u], c, 0, w}; 35         head[u] = pos; 36         e[++pos] = (edge){u, head[v], c, c, -w}; 37         head[v] = pos; 38     } 39      40     bool spfa(){ 41         memset(dis, 0x3f, sizeof(dis)); 42         memset(used, 0, sizeof(used)); 43         used[S] = true; 44         while (!q.empty()) 45             q.pop(); 46         q.push(S); 47         dis[S] = 0; 48         while (!q.empty()){ 49             int x = q.front(); 50             //printf("Now : %d\n", x); 51             for (int i = head[x]; i; i = e[i].ne){ 52                 int y = e[i].x; 53                 if (e[i].c > e[i].f && dis[x] + e[i].w < dis[y]){ 54                     dis[y] = dis[x] + e[i].w; 55                     at[y] = i; 56                     pre[y] = x; 57                     if (!used[y]){ 58                         used[y] = true; 59                         q.push(y); 60                     } 61                 } 62             } 63             used[x] = false; 64             q.pop(); 65         } 66         //printf("Spfa : %d\n", dis[T]); 67         return dis[T] != INF; 68     } 69      70     void update(){ 71         int cut = INF; 72         for (int i = T; i != S; i = pre[i]){ 73             cut = min(cut, e[at[i]].c - e[at[i]].f); 74         } 75         //printf("Cut %d‘s path : %d -> ", T); 76         for (int i = T; i != S; i = pre[i]){ 77             e[at[i]].f += cut; 78             e[at[i] ^ 1].f -= cut; 79             //printf(" - > %d", pre[i]); 80         } 81         quantity += cut; 82         cost += cut * dis[T]; 83         //puts("-------"); 84     } 85      86     void init(int s, int t){ 87         S = s; 88         T = t; 89         pos = 1; 90         quantity = cost = 0; 91         memset(head, 0, sizeof(head)); 92     } 93      94     PII work(){ 95         //puts("Starting"); 96         while (spfa()) 97             update(); 98         //printf("%d %d\n", quantity, cost); 99         return make_pair(quantity, cost);100     }101 }flow;102 103 int main(){104     int n, m, k, x, S, T;105     while (scanf("%d%d%d", &n, &m, &k) == 3){106         if (m > n)107             m = n;108         flow.init(S = n - m + 2, T = n - m + 3);109         for (int i = 1; i <= n - m + 1; ++i)110             flow.adde(i - 1, i, k, 0);111         flow.adde(S, 0, k, 0);112         flow.adde(n - m + 1, T, k, 0);113         for (int i = 1; i <= n; ++i){114             scanf("%d", &x);115             flow.adde(max(0, i - m), min(n - m + 1, i), 1, -x);116         }117         PII ans = flow.work();118         printf("%d\n", -ans.second);119     }120     121     return 0;122 }

第二种建图法,貌似是当年高中某大神秒掉这道题的思路,感觉确实牛逼

点还是和上面一样的建法,边除了流量权值也一样

先定义一个较大值U,比INF小

对于相邻的区间,连接一条容量为U - (m - k),权值为0的边

对于每个点,能包括它的最左边的区间向这个区间无交集的下一个区间连一条边,权值为这个点的权值(注意不是负的了),流量为1

源点对于0这个区间的点加一条U容量,0权值的边,T对最后一个区间加一条U容量,0权值的边

最后的答案就是sum(所有点的权值的和)减去最小费用流的费用

想发和上面那中个人感觉差异挺大的,

对于每个区间,我不切m-k个,而且还是至少不切m-k个,且使不切的水果权值尽可能低

  1 #include <iostream>  2 #include <algorithm>  3 #include <cstdio>  4 #include <cstdlib>  5 #include <cstring>  6 #include <cassert>  7 #include <cmath>  8 #include <map>  9 #include <set> 10 #include <queue> 11 #include <deque> 12 #include <vector> 13 #include <string> 14  15 using namespace std; 16  17 typedef long long LL; 18 typedef pair <int, int> PII; 19  20 const int N = 1e3 + 7; 21 const int M = N * 10; 22 const int INF = 0x3f3f3f3f; 23 const int U = 0x7ffff; 24 const int MOD = 1e9 + 7; 25 const double EPS = 1e-12; 26 const double PI = acos(0) * 2; 27  28 struct edge{ 29     int x, ne, c, f, w; 30 }; 31  32 struct MinCostFlow{ 33     edge e[M]; 34     int head[N], at[N], pre[N], dis[N], S, T, cost, flow, pos; 35     queue <int>Q; 36     bool used[N]; 37      38     void push(int u, int v, int c, int w){ 39         //printf("Add edge %d - > %d c %d w %d\n", u, v, c, w); 40         e[++pos] = (edge){v, head[u], c, 0, w}; 41         head[u] = pos; 42         e[++pos] = (edge){u, head[v], c, c, -w}; 43         head[v] = pos; 44     } 45      46     void init(int s, int t){ 47         S = s; 48         T = t; 49         pos = 1; 50         cost = flow = 0; 51         memset(head, 0, sizeof(head)); 52     } 53      54     bool spfa(){ 55         memset(dis, 0x3f, sizeof(dis)); 56         memset(used, 0, sizeof(used)); 57         while (!Q.empty()) 58             Q.pop(); 59         used[S] = true; 60         Q.push(S); 61         dis[S] = 0; 62         while (!Q.empty()){ 63             int x = Q.front(), y; 64             for (int i = head[x]; i; i = e[i].ne) 65                 if (e[i].c > e[i].f && dis[y = e[i].x] > dis[x] + e[i].w){ 66                     dis[y] = dis[x] + e[i].w; 67                     pre[y] = x; 68                     at[y] = i; 69                     if (!used[y]){ 70                         used[y] = true; 71                         Q.push(y); 72                     } 73                 } 74             Q.pop(); 75             used[x] = false; 76         } 77         return dis[T] != INF; 78     } 79      80     void update(){ 81         int cut = INF; 82         for (int i = T; i != S; i = pre[i]){ 83             cut = min(cut, e[at[i]].c - e[at[i]].f); 84         } 85         //printf("Cut path : \n"); 86         for (int i = T; i != S; i = pre[i]){ 87             e[at[i]].f += cut; 88             e[at[i] ^ 1].f -= cut; 89             //printf("%d ", i); 90         } 91         //printf("%d\n", S); 92         //printf("Cut %d %d\n", cut, dis[T]); 93         flow += cut; 94         cost += cut * dis[T]; 95         //cout << cost << endl; 96     } 97      98     PII work(){ 99         while (spfa())100             update();101         return make_pair(flow, cost);102     }103 }flow;104 105 int main(){106     int n, m, k, sum, S, T, x;107     while (scanf("%d%d%d", &n, &m, &k) == 3){108         if (n < m)109             m = n;110         S = n - m + 2;111         T = n - m + 3;112         flow.init(S, T);113         for (int i = 1; i <= n - m + 1; ++i){114             flow.push(i - 1, i, U - (m - k), 0);115         }116         flow.push(S, 0, U, 0);117         flow.push(n - m + 1, T, U, 0);118         sum = 0;119         for (int i = 1; i <= n; ++i){120             scanf("%d", &x);121             sum += x;122             flow.push(max(0, i - m), min(i, n - m + 1), 1, x);123         }124         PII ans = flow.work();125         printf("%d\n", sum - ans.second);126     }127     128     return 0;129 }

附上一道类似的题目poj 3680