DZY 's BLOG

Safe Travel
Time Limit: 20000 ms Memory Limit: 65536 KB

Description
Gremlins最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚_1)走到别的牛棚(牛_i的目的地是牛棚_i).每一个gremlin只认识牛_i并且知道牛_i一般走到牛棚_i的最短路经.所以它们在牛_i到牛棚_i之前的最后一条牛路上等牛_i. 当然,牛不愿意遇到Gremlins,所以准备找一条稍微不同的路经从牛棚_1走到牛棚_i.所以,请你为每一头牛_i找出避免gremlin_i的最短路经的长度.
和以往一样, 农场上的M (2 <= M <= 200,000)条双向牛路编号为1..M并且能让所有牛到达它们的目的地, N(3 <= N <= 100,000)个编号为1..N的牛棚.牛路i连接牛棚a_i(1 <= a_i <= N)和b_i (1 <= b_i <= N)并且需要时间t_i (1 <=t_i <= 1,000)通过.没有两条牛路连接同样的牛棚,所有牛路满足a_i!=b_i.在所有数据中,牛_i使用的牛棚_1到牛棚_i的最短路经是唯一的.
以下是一个牛棚,牛路和时间的例子:

Input
* 第一行: 两个空格分开的数, N和M
* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i

Output
* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.

Sample Input
4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3

Sample Output
3
3
6

由于题目说了1到没个点的最短路是唯一的。那么这些最短路组成的一棵树-Shortest Path Tree也是唯一的。

dijkstra+heap跑一遍。处理出dist数组。建好SPT。树根当然是1。

对于一个结点u。它的父亲设为p。那么根据题意，从1到u的次短路不能经过<p,u>这条边。

①先沿着SPT的边从1走到v。然后通过一条不是SPT的边，走到u本身。

②先沿着SPT的边从1走到v。然后通过一条不是SPT的边，走到u在SPT中的子孙，再沿着SPT上的边就可以走到u了。

考虑给每个节点挂一个可并堆。（二项堆写起来略烦，还是学习了左偏树）

先解决叶子节点u。

叶子节点肯定是上述的第①种情况。

那么把u出发的不是SPT的边<v,u,w>放入一个小根堆中。那么Ans[u]=min{dist[v]+w}。就是堆顶元素。

然后处理非叶子节点u'。

同样，把u'出发的不是SPT的边<v,u',w>放入一个小根堆中。

因为有情况②的存在，所以节点u'的堆要和它所有的儿子v'的堆合并。v'堆合并时要先加上<v',u'>的边权。然后再取出最大值。

为了方便起见，处理节点u时，添加非SPT中的边时，可以把key设为dist[v]+w(v,u)+dist[u]。

如果到了处理u'时取出这个答案的话，Ans[u']=key-dist[u']。（dist[u]-dist[u']就是上述的加上的边权，这样就不用每次合并的时候逐一加了）

还有就是要注意。如果堆顶选出来的这条非SPT边<u,v>，LCA(u,v)在是当前节点的祖先。那就不可行了。这样必定要经过<p,u>边。不合题意。所以不停地删，直到堆顶元素符合。

左偏树中删除堆顶节点的简单办法就是Merge(rt.l,rt.r)了~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 110000,maxm = 510000,inf = 1061109657;
struct node{
    int x,dis;
    node(){};
    node(int _x,int _d):x(_x),dis(_d){};
    inline bool operator < (node b)const{
        return dis < b.dis;
    }
}H[maxn];
int pos[maxn]={0},rt[maxm],An[maxn],dfn[maxn],path[maxn],size = 0,ee = 0,cnt = 0;
int h[maxn],p[maxm],w[maxm],n1[maxm],d[maxn],vis[maxn],D[maxn],tot = 0,n,m;
struct lt{
    int l,r,d,id;
}L[maxm];
inline void sw(int a,int b){
    pos[H[a].x] = b;
    pos[H[b].x] = a;
    swap(H[a],H[b]);
}
#define pt (x >> 1)
#define ls (x << 1)
#define rs (x << 1 | 1)
void up(int x){
    if(x == 1)  return;
    if(H[x] < H[pt])    sw(x,pt),up(pt);
}
void down(int x){
    int s = x;
    if(ls <= size && H[ls] < H[x])  s = ls;
    if(rs <= size && H[rs] < H[s])  s = rs;
    if(s != x)  sw(x,s),down(s);
}
void del(int x){
    sw(x,size);
    size --;
    up(x);
    down(x);
}
void ins(node a){
    H[++ size] = a;
    pos[a.x] = size;
    up(size);
}
void dijkstra(int s){
    size = d[s] = 0;
    ins(node(s,0));
    while(size){
        node u = H[1];
        pos[H[1].x] = 0;
        del(1);
        if(vis[u.x])    continue;
        vis[u.x] = 1;
        for(int i = h[u.x];~i;i = n1[i])    if(!vis[p[i]])
            if(u.dis + w[i] < d[p[i]]){
                d[p[i]] = u.dis + w[i];
                path[p[i]] = u.x;
                if(pos[p[i]]){
                    H[pos[p[i]]].dis = d[p[i]];
                    up(pos[p[i]]);
                }else   ins(node(p[i],d[p[i]]));
            }
    }
}
inline void ae(int a,int b,int c){
    p[ee] = b;  w[ee] = c;  n1[ee] = h[a];  h[a] = ee ++;
    p[ee] = a;  w[ee] = c;  n1[ee] = h[b];  h[b] = ee ++;
}
int merge(int a,int b){
    if(!a || !b)    return max(a,b);
    if(L[a].d > L[b].d) swap(a,b);
    L[a].r = merge(L[a].r,b);
    if(D[L[a].r] > D[L[a].l])   swap(L[a].l,L[a].r);
    if(L[a].r == 0) D[a] = 0;
    else     D[a] = D[L[a].r] + 1;
    return a;
}
void dfs(int u,int fa){
    dfn[u] = ++ tot;
    for(int i = h[u]; ~i;i = n1[i]){
        if(p[i] == fa)  continue;
        if(path[p[i]] == u){
            dfs(p[i],u);
            rt[u] = merge(rt[u],rt[p[i]]);
        }
    }
    for(int i = h[u]; ~i;i = n1[i]){
        if(p[i] == fa)  continue;
        if(path[p[i]] != u){
            L[++ cnt] = (lt){0,0,d[u]+w[i]+d[p[i]],p[i]};
            rt[u] = merge(rt[u],cnt);
        }
    }
    while(rt[u] && dfn[L[rt[u]].id] >= dfn[u])
        rt[u] = merge(L[rt[u]].l,L[rt[u]].r);
    An[u] = rt[u] ? L[rt[u]].d - d[u] : -1;
}
    
int main(){
    memset(h,0xff,sizeof(h));
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i = 1;i <= m;i ++){
        scanf("%d%d%d",&u,&v,&w);
        ae(u,v,w);
    }
    memset(d,63,sizeof(d));
    dijkstra(1);
    dfs(1,0);
    for(int i = 2;i <= n;i ++)  printf("%d\n",An[i]);
    return 0;
}

Description
When Farmer John isn't milking cows, stacking haybales, lining up his cows, or building fences, he enjoys sitting down with a good book. Over the years, he has collected N books (1 <= N <= 2,000), and he wants to build a new set of bookshelves to hold them all.

Each book i has a width W(i) and height H(i). The books need to be added to a set of shelves in order; for example, the first shelf should contain books 1...k for some k, the second shelf should start with book k+1, and so on. Each shelf can have a total width of at most L (1 <= L <= 1,000,000,000). The height of a shelf is equal to the height of the tallest book on that shelf, and the height of the entire set of bookshelves is the sum of the heights of all the individual shelves, since they are all stacked vertically.

Please help FJ compute the minimum possible height for the entire set of bookshelves.
Input
* Line 1: Two space-separated integers: N and L.

* Lines 2..1+N: Line i+1 contains two space-separated integers: H(i) and W(i). (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).
Output
* Line 1: The minimum possible total height for the set of bookshelves.
Sample Input
5 10
5 7
9 2
8 5
13 2
3 8

INPUT DETAILS:

There are 5 books. Each shelf can have total width at most 10.
Sample Output
21

OUTPUT DETAILS:

There are 3 shelves, the first containing just book 1 (height 5, width 7), the second containing books 2..4 (height 13, width 9), and the third containing book 5 (height 3, width 8).

【Silver难度】：N<=2000

很容易就看出DP了。

令C[i]表示放到第i本书的最小代价。

很明显C[i] = min{max{H[j+1..i]} + C[j]}。(sigma{L[j+1..i]}<=L,0<=j<i)。

那么O(N^2)这道题就过了。

【Gold难度】：N<=100000

目前已被虐傻