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

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

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

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

程序请看我的空间

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

破题！！！！！！！！！！！！！！！！！！！！！！！！！

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

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

交了16遍！！！！！！！！！！！！！！！！！！！！！！！

输出一定要：

for i:=1 to n do

if vis[i] then

write(i,':Yes')

else write(i,':No');

writeln;

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

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

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

如果你的程序不够快，不要用writeln！！！

如果你的程序够快，不要随便用writeln！！！

用write没有任何问题！！！

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

干嘛用write？！！！！！！！！！！！！！

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

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

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

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

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

最后，fOrmkNight通过。。。

第十四个。。。

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

B

F

S

O

R

F

L

O

O

D

F

I

L

L

貌似连天花板也没有了

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

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

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

N次90分啊……

这题咋整?才60分啊..

怎么回事?????

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

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

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

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

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

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

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

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

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

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

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