CSAcademy Round #83 (Div. 2 only) Firestarter

题目链接https://csacademy.com/contest/round-83/task/firestarter/

题意:给定一张连通的无向图(不存在重边和自环),我们把连接的边看作一条线,线两端当作节点,无向图的边权即线的边长,现在给你若干个操作,每个操作由t,a,b,l四个参数组成,含义即在a-b这条边上我们在时间t的时候在距离al处点火,此后这个火就向两端开始燃烧,如果烧到节点,那么接下来与该节点相连的所有边也都开始着火并开始蔓延到远处,问需要多少时间整张图会被烧完。

思路:附上官方题解:https://csacademy.com/contest/round-83/task/firestarter/solution/
,已经讲的很详细了,主要考虑到每个点越早被烧到的话之后这个点就没用了,符合最短路的特性,所以只要我们能够预处理出每个点最早烧到的时间就可以处理答案了。然后我们又把所有的点火事件看做在这条边上相当于加了一个节点,t时刻被点燃我们可以建立一个虚拟源点连向这些节点并把边权设为t,然后跑下最短路后我们即可知道每个节点最早被点燃的时间,这个时候我们只要算出一条边被烧完的时间然后取max就是我们要的答案了,考虑两个节点aba开始烧的时间是T_a,T_b开始烧的时间是T_bT_a\leq T_b,线长为L,那么刚开始只有a在烧,经过T_b-T_ab开始烧,所以一条线被烧完的时间就是T_a+T_b-T_a+\frac{L-(T_b-T_a)}{2}

#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=3e5+10;
struct Edge{
    int u,v,w,offset;
    vector<int> specialPoints;

    int getSpecialPointIndex(int u,int v,int l){
        if (u>v) l=w-l;
        return offset+lower_bound(specialPoints.begin(),specialPoints.end(),l)-specialPoints.begin();
    }
};
struct Firestarter{int t,a,b,l;};
vector<Firestarter>updates;
map<pair<int,int>,Edge>mp;
vector<pair<int,int> >G[N];
int n,m,q,t,u,v,w,i,numGoodNode;
ll dis[N];
void createSpecialPoints(){
    for (int i=0;i<(int)updates.size();i++){
        Firestarter& e=updates[i];
        int a=e.a,b=e.b,l=e.l;
        bool swapped=0;
        if (a>b){
            swap(a,b);
            swapped=1;
        }
        Edge& edge=mp[MP(a,b)];
        if (swapped) l=edge.w-l;
        edge.specialPoints.PB(l);
    }
    for (auto& e:mp){
        Edge& rhs=e.second;
        sort(rhs.specialPoints.begin(),rhs.specialPoints.end());
        rhs.specialPoints.erase(unique(rhs.specialPoints.begin(),rhs.specialPoints.end()),rhs.specialPoints.end());
        rhs.offset=n+1;
        n+=rhs.specialPoints.size();
    }
}
void createGraph(){
    for (auto& itr:mp){
        Edge& rhs=itr.second;
        int lastNode=rhs.u,lastPos=0;
        for (int i=0;i<(int)rhs.specialPoints.size();i++){
            int curNode=rhs.offset+i,curPos=rhs.specialPoints[i];

            int pos=curPos-lastPos;
            G[lastNode].PB(MP(curNode,pos));
            G[curNode].PB(MP(lastNode,pos));
            lastNode=curNode;
            lastPos=curPos;
        }
        int curNode=rhs.v,curPos=rhs.w;
        int pos=curPos-lastPos;
        G[curNode].PB(MP(lastNode,pos));
        G[lastNode].PB(MP(curNode,pos));
    }
}
void createVirtualNode(){
    for (auto& itr:updates){
        int u=itr.a;
        int v=itr.b;
        if (u>v) swap(u,v);
        int specialPoints=mp[MP(u,v)].getSpecialPointIndex(itr.a,itr.b,itr.l);
        int myNode=++n;
        G[specialPoints].PB(MP(myNode,itr.t));
        G[myNode].PB(MP(specialPoints,itr.t));
    }
}
void dijkstra(){
    priority_queue<pair<ll,int> >Q;
    for (int i=1;i<=n;i++) dis[i]=1000000000000000000LL;
    for (int i=numGoodNode+1;i<=n;i++){
        dis[i]=0;
        Q.push(MP(0,i));
    }
    while (!Q.empty()){
        pair<ll,int> cur=Q.top();Q.pop();

        int u=cur.second;
        ll cost=-cur.first;
        if (dis[u]!=cost) continue;
        for (auto& itr:G[u]){
            int v=itr.first;
            ll w=itr.second;
            if (dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                Q.push(MP(-dis[v],v));
            }
        }
    }
}
bool isVirtual(int node){return node>numGoodNode;}
int main(){
    read(n),read(m),read(q);
    for (i=1;i<=m;i++){
        read(u),read(v),read(w);
        if (u>v) swap(u,v);
        mp[MP(u,v)]=(Edge){u,v,w,0};
    }
    for (i=1;i<=q;i++){
        read(t),read(u),read(v),read(w);
        updates.PB((Firestarter){t,u,v,w});
    }
    createSpecialPoints();
    createGraph();
    numGoodNode=n;
    createVirtualNode();
    dijkstra();

    double res=0;
    for (u=1;u<=numGoodNode;u++){
        for (auto& e:G[u]){
            int v=e.first;
            int w=e.second;
            ll a=dis[u];
            ll b=dis[v];

            if (isVirtual(u)||isVirtual(v)) continue;

            ll diff=a-b;
            diff=abs(diff);
            res=max(res,max(a,b)+(w-diff)/2.0);
        }
    }
    printf("%.1lf\n",res);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注