/ Vijos / 题库 / 魔塔 /

题解

45 条题解

  • 1
    @ 2018-11-08 12:42:18

    Bellman_Ford+vector+链式前向星

    vector中存当前有那些点可以到

    链式前向星存边

    来跑Bellman_Ford

    当一个点的所有邻点已经在队列中时,给它打上lazy mark(懒惰标记,类似线段树),下次遍历时直接跳过,这样可以卡过链式图

    结果可想而知,被菊花图卡了

    如果有哪位大佬想到了SPFA或SLF的方法,请联系我,谢谢

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    
    ll n,s,m,v[100010];
    ll ver[100010],edge[100010],head[100010],Next[100010],tot;
    bool b[100010];
    
    inline void addEdge(ll x,ll y,ll z){//链式前向星存边
        ver[++tot]=y;
        edge[tot]=z;
        Next[tot]=head[x];
        head[x]=tot;
    }
    
    inline bool check(ll x){
        for(ll i=head[x]; i; i=Next[i]){//遍历每一个邻点
            if(v[ver[i]]==false) return false;//有尚未入队的就还要把他保留在队中
        }
        return true;
    }
    
    inline void Bellman_Ford(ll s){
        vector<ll> q;//哪些点可以达到
        q.push_back(s); v[s]=true;//起点入队
        while(true){
            bool bo=true;
            for(ll k=0; k<q.size(); k++){//遍历所有点
                ll x=q[k];//记下当前点
                if(b[k]){//还要走
                    if(check(x)){
                        b[k]=false;
                        continue;
                    }
                     
                    for(ll i=head[x]; i; i=Next[i]){//遍历所有边
                        ll y=ver[i],z=edge[i];
                        if(v[z]){//可以走
                            if(v[y]==false){//没走过
                                q.push_back(y);//入队
                                v[y]=true;//走过了
                                bo=false;//还要继续做
                            }
                        }
                    }   
                }
                
            }
            if(bo) break;//无法继续拓展图,直接退出
        }
    }
    
    int main(){
        scanf("%lld %lld %lld",&n,&s,&m);
        while(m--){
            ll x,y,z;
            scanf("%lld %lld %lld",&x,&y,&z);
            addEdge(x,y,z);
            addEdge(y,x,z);
        }
        memset(b,true,sizeof(b));
        Bellman_Ford(s);
        for(ll i=1; i<=n; i++){
            printf("%lld:",i);
            if(v[i]) puts("Yes");
            else puts("No");
        }
        return 0;
    }
    

    update 1:
    问题解决了
    边的存储方式改一下,用vector存,每一条边在扫描后直接删除
    注意:因为vector删除的特性,vector的扫描要从后向前

    代码:

    #include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    
    ll n,s,m,v[100010];
    bool b[100010];
    struct node{
        ll To,length;
    };
    vector<node> edge[100010];
    
    inline void addEdge(ll x,ll y,ll z){
        edge[x].push_back(node{y,z});
    }
    
    inline bool check(ll x){
        for(ll i=0; i<edge[x].size(); i++){
            if(v[edge[x][i].To]==false) return false;
        }
        return true;
    }
    
    inline void Bellman_Ford(ll s){
        vector<ll> ver;
        ver.push_back(s);
        v[s]=true;
        bool bo=false;
        while(!ver.empty()){
            bo=false;
            for(ll k=ver.size()-1; k>=0; k--){
                ll x=ver[k];
                if(check(x)){
                    ver.erase(ver.begin()+k);
                    continue;
                }
                     
                for(ll i=edge[x].size()-1; i>=0; i--){
                    ll y=edge[x][i].To,z=edge[x][i].length;
                    if(v[z]){
                        edge[x].erase(edge[x].begin()+i);
                        if(v[y]==false){
                            ver.push_back(y);
                            v[y]=true;
                            bo=true;
                        }
                    }
                }
            }
            if(bo==false) break;
        }
    }
    
    int main(){
        scanf("%lld %lld %lld",&n,&s,&m);
        while(m--){
            ll x,y,z;
            scanf("%lld %lld %lld",&x,&y,&z);
            addEdge(x,y,z);
            addEdge(y,x,z);
        }
        
        Bellman_Ford(s);
        for(ll i=1; i<=n; i++){
            printf("%lld:",i);
            if(v[i]) puts("Yes");
            else puts("No");
        }
        return 0;
    }
    
  • 1
    @ 2015-05-12 15:15:56

    妈呀!vector强行被卡掉、、要数组模拟链表、、

    • @ 2018-11-08 12:43:07

      写法问题,我用vector过了

  • 1
    @ 2014-11-03 21:06:35

    我AC了,今天晚上发题解,博客:http://blog.csdn.net/vmurder
    嗯,不是强剪枝,是O(n+m),而且很好写。

  • 1
    @ 2009-10-27 20:51:10

    本题困难之处在于如何才能不重复地BFS。我是这样优化的,当某个点连出去的点j由于缺少钥匙i不能到时,就把j点加入到数组i中,然后当i被走到时,直接把数组i中的元素加入到BFS队尾,编程中要注意已经入队的点别让它第二次入队,这样保证了每个点只入一次队,因此总时间最多就是O(n)了。

    程序请看我的空间

    http://hi.baidu.com/cloudygoose/blog/item/3cfc137f6d361d320dd7dad6.html

  • 0
    @ 2009-07-12 10:31:33

    破题!!!!!!!!!!!!!!!!!!!!!!!!!

    本来记事本就AC了,结果因为行末没有换行就给卡了!!!!

    白白的浪费了2个小时!!!!!!!!!!!!!!!!!

    交了16遍!!!!!!!!!!!!!!!!!!!!!!!

    输出一定要:

    for i:=1 to n do

    if vis[i] then

    write(i,':Yes')

    else write(i,':No');

    writeln;

  • 0
    @ 2009-02-26 18:55:40

    千万不要用writeln,题目是可以用write的,虽然我也想不通用write是怎么换行的!!!!也许根本就不用换行!!!!!

    ~~~~~~~~阴人的数据~~~~~~~~~~~

  • 0
    @ 2009-03-20 23:59:24

    天啊,把 \n 去了就ac了..

  • 0
    @ 2007-10-29 19:13:44

    如果你的程序不够快,不要用writeln!!!

    如果你的程序够快,不要随便用writeln!!!

    用write没有任何问题!!!

  • 0
    @ 2007-09-28 20:45:56

    千万不要用writeln!!!!!!!!!我因此wa了n次!!!

  • 0
    @ 2007-07-31 12:39:29

    干嘛用write?!!!!!!!!!!!!!

    真是BT……………………………………………………………………………………………………

  • 0
    @ 2007-07-19 23:42:24

    回答hzr同学:意思是删掉一条边。具体是第m条边覆盖第i条边,然后删去第m条边,效果就是删去第i条边

  • 0
    @ 2007-04-17 16:51:40

    我用整整20次的提交证明了floodfill这条路行不通

  • 0
    @ 2007-03-27 13:18:29

    最后一个数据,就输出40003个Yes就可以了。。。

    一共交了约40次,最后,我的LYZ。。。。

    最后,fOrmkNight通过。。。

    第十四个。。。

  • 0
    @ 2007-03-14 20:22:30

    我想用图的连通就能解体吧

  • 0
    @ 2007-02-03 13:42:59

    B

    F

    S

    O

    R

    F

    L

    O

    O

    D

    F

    I

    L

    L

  • 0
    @ 2007-01-10 19:42:31

    貌似连天花板也没有了

  • 0
    @ 2007-01-10 17:11:12

    不做了,不做了。这题让我的正确率下降了5%(不包括小号提交的那10多次)。

    始终没搞懂最后一个数据为什么莫名其妙地超时……

    我用链表,然后不断维护。

    N次90分啊……

  • 0
    @ 2007-01-10 11:36:36

    这题咋整?才60分啊..

  • 0
    @ 2007-01-09 22:24:52

    怎么回事?????

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:运行时错误...| 错误号: 202 | 堆栈溢出错

    ├ 测试数据 08:运行时错误...| 错误号: 202 | 堆栈溢出错

    ├ 测试数据 09:运行时错误...| 错误号: 202 | 堆栈溢出错

    ├ 测试数据 10:运行时错误...| 错误号: 202 | 堆栈溢出错

  • 0
    @ 2007-01-09 17:17:09

    Vivid Puppy也太强了吧,搜索都0秒(我在机子上至少要1分钟)

信息

ID
1321
难度
8
分类
搜索 | 图结构 点击显示
标签
(无)
递交数
966
已通过
124
通过率
13%
被复制
2
上传者