【NOI2014】魔法森林

Published on 2017 Jul 15 20:17:45
Last Updated on 2017 Jul 17 15:18:10

UOJ 2W BZOJ 1A
UOJ传送门

麻麻UOJ ExT卡我QAQ 正常NOI的10个数据是可以过的QAQ

最基本的思路
先枚举最大边的a值(先按a值对边排个序,然后依次加入图)
问题就是对于每个a值求最小需要的b值,然后加一起更新ans值 ←我与std就重合到这QAQ
一个一个枚举?辣鸡
二分?感觉还不如枚举QAQ
SPFA求?要是每次都从头来一次的话一定很慢
所以记录上一次SPFA结果,每次从新加的边的两端开始更新,具体见代码
酱紫一道数据结构题就这样被糟蹋成了一道CC黑暗算法题目QAQ

附:std做法
对于一个a值就是求个最小生成树
这样搞个LCT维护路径最大边的位置
加入新边的时候把边上最大边删除掉,还是最小生成树
我好弱呀我连Spaly都不会写,更别说LCT了QAQ

#include <bits/stdc++.h>
using namespace std;
const int N=50005,E=200005,inf=0x3f3f3f3f;
struct Edge{
    int f,t,a,b;
    Edge(){}
    Edge(int f,int t,int a,int b):f(f),t(t),a(a),b(b){}
    bool operator<(const Edge& e)const{
        return a<e.a;
    }
}edge[E],edge2[E];
int n,m,esz;
vector<int> G[N];
void adde(Edge x){
    edge[++esz]=x;
    G[x.f].push_back(esz);
    swap(x.f,x.t);
    edge[++esz]=x;
    G[x.f].push_back(esz);
}
int d[N],vis[N];
queue<int> Q;
void spfa(){
    while(!Q.empty()){
        int x=Q.front();Q.pop();
        //printf("front %d:d=%d\n",x,d[x]);
        for(int i=0;i<G[x].size();i++){
            Edge&e=edge[G[x][i]];
            if(d[e.t]>max(d[x],e.b)){
                d[e.t]=max(d[x],e.b);
                if(!vis[e.t])
                    Q.push(e.t),vis[e.t]=1;
            }
        }
        vis[x]=0;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&edge2[i].f,&edge2[i].t,&edge2[i].a,&edge2[i].b);
    }
    sort(edge2+1,edge2+m+1);
    int ans=inf;
    d[1]=0;
    for(int i=2;i<=n;i++) d[i]=inf;
    for(int i=1;i<=m;i++){
        //for(int j=1;j<=n;j++) printf("d[%d]=%d\n",j,d[j]);
        adde(edge2[i]);
        Q.push(edge2[i].f),vis[edge2[i].f]=1;
        Q.push(edge2[i].t),vis[edge2[i].t]=1;
        spfa();
        ans=min(ans,edge2[i].a+d[n]);
    }
    if(ans==inf) printf("-1");
    else printf("%d\n",ans);
}