首页 > 代码库 > codeforces 434D

codeforces 434D

2024-07-30 04:21:57   223人阅读

题意：有n<=50个点，每个点有xi有[li, ri]种取值，-100 <= li <= ri <= 100,并且给定m<=100条边，每条边为u，v,d表示xu<=xv+d。

        每个点value fi(x) = ai*x^2 + bi*x + ci。现在求一种合法的方案，使得权值和最大。

思路：先不考虑的xu<=xv + d。那么建图：

       首先考虑到每个点的权值可能为负，并且求最大与最小割相反，

        所以先 取反再+oo（一个很大的数），最后再减掉即可

        对于每个点，拆成ri-li+1个点，

        对于第k个点，node(k, i)表示第k个点值为i对应的标号

        值为i-1跟i连一条边<node（k, i-1）, node(k, i),  oo - f(k, i)>的边，

        S到第一个点连<S, node(k, l[k]), f(k, l[k])>

       最后一个点到T连<node(k，r[k]), Inf>

       那么很明显n*oo-最小割就是答案。。

       但是如果有了限制条件xu<=xv + d,我们怎么把限制条件加到图上呢？

       对于一对关系，xu<=xv+d

       考虑到点u，如果node(u, i)到node（u,i+1）之间的边在割集里,那么说明xu=i+1

       也就是说如果xv<xu-d是非法的，也就是说对于v在xu-d之前出现割是非法的。

       那么我们可以连<node(u,i), node(v, i-d)， Inf>的边，使得方案合法。。

code：

 1 #include <bits/stdc++.h> 2 using namespace std; 3 #define M0(a) memset(a, 0, sizeof(a)) 4 #define Inf 0x3fffffff 5 const int maxn = 20010; 6 const int maxm = 900010; 7 const int big = 15000000; 8 struct oo{ 9     int y, f, next;10 };11 struct MaxFlow{12        int n, S, T, tot;13        int son[maxn], dist[maxn], gap[maxn];14        oo e[maxm];15        int sap(int x, int aug){16            if (x == T) return aug;17            int mind = n;18            int sum = 0, f;19            for (int p = son[x]; p != -1; p = e[p].next){20                   int y = e[p].y;21                   if (dist[y] + 1 == dist[x] && e[p].f){22                        f = sap(y, min(e[p].f, aug - sum));23                        e[p].f -= f;24                        e[p^1].f += f;25                        sum += f;26                        if (sum == aug || dist[S] >= n) return sum;27                   }28                   if (e[p].f) mind = min(mind, dist[y]);29            }30            if (!sum){31                if (!(--gap[dist[x]])) dist[S] = n;32                ++gap[dist[x] = mind + 1];33            }34            return sum;35        }36        void add(int x, int y, int f){37             e[tot].y = y; e[tot].f = f;38             e[tot].next = son[x]; son[x] = tot++;39             e[tot].y = x; e[tot].f = 0;40             e[tot].next = son[y]; son[y] = tot++;41        }42 43        void init(int S, int T, int n){44             memset(son, -1, sizeof(son));45             tot = 0;46             this->S = S, this->T = T, this->n = n;47        }48        int maxflow(){49             M0(gap);50             M0(dist);51             gap[0] = n;52             int ans = 0;53             while (dist[S] < n) ans += sap(S, Inf);54             return ans;55        }56 } F;57 int S, T;58 int n, m, a[120], b[200], c[200], l[200], r[200];59 inline int f(const int&k, const int& x){60      return big - (a[k] * x * x + b[k] * x + c[k]);61 }62 63 inline int node(const int&k, const int& x){64      return x == l[k] - 1 ? S : (k-1) * 201 + x + 101;65 }66 67 void solve(){68      for (int i = 1; i <= n; ++i) scanf("%d%d%d", &a[i], &b[i], &c[i]);69      for (int i = 1;  i<= n; ++i) scanf("%d%d", &l[i], &r[i]);70      S = 0, T = 201 * n + 1;71      F.init(S, T, T + 1);72      for (int i = 1; i <= n; ++i){73          for (int j = l[i]; j <= r[i]; ++j)74              F.add(node(i, j-1), node(i, j), f(i, j));75          F.add(node(i, r[i]), T, Inf);76      }77      int u, v, d;78      int x;79      for (int i = 1; i <= m; ++i){80           scanf("%d%d%d", &u, &v, &d);81           for (int j = l[v]; j <= r[v]; ++j) if (j + d <= r[u]){82                   x = j + d;83                   if (x < l[u]) x = l[u] -1;84                   F.add(node(u, x), node(v, j), Inf); 85           }86      }87      int ans = big * n;88      ans -= F.maxflow();89      cout << ans << endl;90 }91 92 int main(){93 //    freopen("a.in", "r", stdin);94     while (scanf("%d%d", &n, &m) != EOF){95         solve();96     }            97 }
View Code

 

codeforces 434D


联系
我们