首页 > 其他 > 详细

LA 3683 A Scheduling Problem

时间:2020-02-23 22:50:26      阅读:41      评论:0      收藏:0      [点我收藏+]

标签:clu   父亲   queue   span   return   hid   

二分答案+树形dp

可以在 x 天内完成,就可以在 x + k (k >= 1) 天内完成

那么考虑二分天数 m , 验证是否可行

也就是考虑给无向边定向,树中最长链的长度是否能小于 m

记儿子指向父亲的边为正向边,父亲指向儿子的边为反向边

对于任意一条链,它经过的深度最浅的点是唯一的 (不妨记为u)

那么这条链必然在以 u 为根的树中,

且必然由一段终点为u的正向边和一段起点为u的反向边组成

记 f[u] 表示在以 u 为根的树中,满足最长链长度小于 m, 终点为u的正向最长链的长度最小是多少

记 g[u] 表示在以 u 为根的树中,满足最长链长度小于 m, 起点为u的反向最长链的长度最小是多少

//若不存在,值为inf

对于定向边:

g[u] = max(g[v] + 1) (u -> v)  f[u] = max(f[v] + 1) (v -> u)

对于反向边 (u -- v):

由于每条边只能更新 f, g 之一,而且一定不会使之变小

以求 f[u] 为例:

将所由 v 按 f[v] 从小到大排序

枚举决策点 p, 则必然将p及其左边的 v 定向为 v->u, 右边的与之相反,更新即可

求 g[u] 差不多一样

最后看 f[root] 是否为 inf即可

技术分享图片
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<fstream>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<deque>
  7 #include<vector>
  8 #include<queue>
  9 #include<string>
 10 #include<cstring>
 11 #include<map>
 12 #include<stack>
 13 #include<set>
 14 using namespace std;
 15 typedef long long LL;
 16 const int N = 405;
 17 
 18 int n, m, f[N], g[N], p, first[N], cnt, root, inf = 0x3f3f3f3f;
 19 struct Edge {
 20     int to, next, k;
 21 } e[N];
 22 struct node {
 23     int g, f;
 24 } a[N];
 25 char s[15];
 26 bool vis[N];
 27 
 28 bool cmp1(node a, node b) { return a.f < b.f; }
 29 
 30 bool cmp2(node a, node b) { return a.g < b.g; }
 31 
 32 void dfs(int u) {
 33     f[u] = g[u] = 0;
 34     int tot = 0, rf = 0, rg = 0;
 35     for(int i = first[u]; i != -1; i = e[i].next) {
 36         int v = e[i].to, k = e[i].k;
 37         dfs(v);
 38         if(k == 1)
 39             g[u] = max(g[v] + 1, g[u]);
 40         if(k == 2) 
 41             f[u] = max(f[u], f[v] + 1);
 42         if(k == 0) {
 43             a[++tot] = (node) { g[v] + 1, f[v] + 1 };
 44             rg = max(rg, g[v] + 1);
 45             rf = max(rf, f[v] + 1);
 46         }
 47     }
 48     if(g[u] + f[u] > m) g[u] = f[u] = inf;
 49     if(!tot) return;
 50     int F = inf, G = inf;
 51     if(f[u] + rg <= m) F = f[u];
 52     if(g[u] + rf <= m) G = g[u];
 53     sort(a + 1, a + tot + 1, cmp1);
 54     int pf = f[u], pg = g[u];
 55     for(int i = 1; i <= tot; i++) {
 56         pf = max(pf, a[i].f);
 57         pg = g[u];
 58         for(int j = i + 1; j <= tot; j++)
 59             pg = max(pg, a[i].g);
 60         if(pf + pg <= m) F = min(F, pf);
 61     }
 62     sort(a + 1, a + tot + 1, cmp2);
 63     pf = f[u], pg = g[u];
 64     for(int i = 1; i <= tot; i++) {
 65         pg = max(pg, a[i].g);
 66         pf = f[u];
 67         for(int j = i + 1; j <= tot; j++)
 68             pf = max(pf, a[i].f);
 69         if(pg + pf <= m) G = min(G, pg);
 70     }
 71     f[u] = F;
 72     g[u] = G;
 73     return;
 74 }
 75 
 76 bool dp() {
 77     memset(f, 0x3f, sizeof(f));
 78     memset(g, 0x3f, sizeof(g));
 79     dfs(root);
 80     return (f[root] >= inf) ? 0 : 1;
 81 }
 82 
 83 void add(int u, int v, int k) {
 84     e[cnt] = (Edge) { v, first[u], k }; 
 85     first[u] = cnt++;
 86 }
 87 
 88 void Read() {
 89     do {
 90         n = max(n, p);
 91         while(cin>>s) {
 92             if(s[0] == 0) break;
 93             int len = strlen(s), to = 0, k = 0;
 94             for(int i = 0; i < len; i++) {
 95                 if(s[i] >= 0 && s[i] <= 9) to = to*10 + s[i] - 0;
 96                 else {
 97                     if(s[i] == u) add(p, to, 2), k = 2;
 98                     else add(p, to, 1), k = 1;
 99                 }
100             }
101             vis[to] = 1;
102             n = max(to, n);
103             if(!k) add(p, to, k);
104         }
105         cin>>p;
106     } while(p != 0);
107 }
108 
109 int main() {
110     while(cin>>p && p) {
111         memset(first, -1, sizeof(first));
112         memset(vis, 0, sizeof(vis));
113         n = p; cnt = 0;
114         Read();
115         for(int i = 1; i <= n; i++)
116             if(!vis[i]) root = i;
117         int l = 0, r = n;
118         while(l < r) {
119             m = (l + r)/2;
120             if(dp()) r = m;
121             else l = m + 1;
122         }
123         printf("%d\n", l + 1);
124     }
125     return 0;
126 }
View Code

 

LA 3683 A Scheduling Problem

标签:clu   父亲   queue   span   return   hid   

原文:https://www.cnblogs.com/ympc2005/p/12354086.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号