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;
}

第一问先求1到n的最短路。第二问求破坏一些路使得1到n的最短路变大。每条路被破坏都要花费一定的代价Ci。求min∑Ci。

我学会了写spfa好开心啊！我学会了写dinic好开心啊！==

破坏边使不连通明显最小割水掉嘛、、

好了言归正传、先求出所有的最短路。然后判断每条边是不是在1~n的最短路上。是的话就连边。然后再新建的图上做最小割。

一开始建图建错了、、应该这么建：首先以1为源点跑spfa，记录d[0][i]为1~i的最短路。然后以n为源点跑spfa，记录d[1][i]为n~i的最短路。

如果i在1~n的最短路上那一定满足d[0][i]+d[1][i]==d[0][n]（这也是第一问的答案、、）且d[0][i]+w(i,j)=d[0][j]。

然后就没了、、继续fread然后刷到rank5、、、

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxm=250000,maxn=505,inf=2000000009;
struct edge{int t,c,next;}E[maxm];
char buf[3000000],*pt=buf;
int p[maxm],w[maxm],c[maxm],n1[maxm],h[maxn],v[maxn],d[2][maxn],q[maxm],V[maxn],level[maxn],n,m,tot=0,tt=0,S,T,An=inf;
inline int getint(){
    int r=0; while(*pt<'0'||*pt>'9')pt++; while(*pt>='0'&&*pt<='9')r=r*10+*pt++-48;return r;
}inline void ae1(int u,int v,int t,int cc){
    p[tot]=v;   w[tot]=t;   c[tot]=cc;  n1[tot]=h[u];   h[u]=tot++;
    p[tot]=u;   w[tot]=t;   c[tot]=cc;  n1[tot]=h[v];   h[v]=tot++;
}inline void ae2(int a,int b,int c){
    E[tt].t=b; E[tt].c=c; E[tt].next=V[a];   V[a]=tt++;
    E[tt].t=a; E[tt].c=0; E[tt].next=V[b];   V[b]=tt++;
}inline int bfs(){
    memset(level,0xff,sizeof(level));   int head=0,tail=1;  q[0]=S; level[S]=1;
    while(head<tail){
        int u=q[head++];    if(u==T)return 1;
        for(int p=V[u];p!=-1;p=E[p].next)
            if(E[p].c>0 && level[E[p].t]==-1) level[E[p].t]=level[u]+1,q[tail++]=E[p].t;
    }return 0;
}int dfs(int u=S,int lmt=inf){
    if(u==T)    return lmt; int ret=0,  delta;
    for(int p=V[u];p!=-1;p=E[p].next){
        if(E[p].c>0 && level[E[p].t]==level[u]+1){
            delta=dfs(E[p].t,min(lmt-ret,E[p].c));
            E[p].c-=delta;  E[p^1].c+=delta;    ret+=delta;
            if(ret==lmt)    return ret;
        }
    }if(!ret)   level[u]=-1;    return ret;
}inline int dinic(){
    int ret=0;S=1,T=n;
    for(int i=1;i<=n;i++)for(int j=h[i];~j;j=n1[j])
        if(d[0][p[j]]+d[1][p[j]]==An && d[0][i]+w[j]==d[0][p[j]]) ae2(i,p[j],c[j]);
    while(bfs())ret+=dfs(); return ret;
}inline void spfa(int SS,int f){
    for(int i=1;i<=n;i++)d[f][i]=inf; memset(v,0,sizeof(v));
    int head=0,tail=1;  q[0]=SS; v[SS]=1; d[f][SS]=0;
    while(head<tail){
        int u=q[head++];    v[u]=0;
        for(int i=h[u];~i;i=n1[i])
            if(d[f][u]+w[i]<d[f][p[i]]){
                d[f][p[i]]=d[f][u]+w[i];  if(!v[p[i]])  v[p[i]]=1,  q[tail++]=p[i];
            }
    }
}int main(){
    fread(pt,1,3000000,stdin);  n=getint(),m=getint();  memset(h,-1,sizeof(h)); memset(V,-1,sizeof(V));
    for(int u,v,t,c,i=1;i<=m;u=getint(),v=getint(),t=getint(),c=getint(),ae1(u,v,t,c),i++);
    spfa(1,0);  spfa(n,1);  for(int i=1;i<=n;i++)   An=min(An,d[0][i]+d[1][i]);
    printf("%d\n%d\n",An,dinic()); return 0;
}