精华内容
下载资源
问答
  • spfa板子

    2019-07-18 09:36:00
    spfa板子 Heap+Dijkstra都会写,突然发现spfa不会写了…… inq[]记录是否已在队列中 inline void spfa(int s){ q.push(s); while(!q.empty()){ int u=q.front();q.pop(); inq[u]=0; for(register int i=head[.....

    spfa板子

    Heap+Dijkstra都会写,突然发现spfa不会写了……

    inq[]记录是否已在队列中

    inline void spfa(int s){
        q.push(s);
        while(!q.empty()){
            int u=q.front();q.pop();
            inq[u]=0;
            for(register int i=head[u];i;i=nxt[i]){
                int v=vv[i];
                if(dis[v]<dis[u]+ww[i]){
                    dis[v]=dis[u]+ww[i];
                    if(!inq[v]) inq[v]=1,q.push(v);
                }
            }
        }
    }

    判负环

    图中无负环时,一个点最多只能被其他点松弛\(n-1\)

    inline bool spfa(int s){
        q.push(s);
        while(!q.empty()){
            int u=q.front();q.pop();
            inq[u]=0;
            for(register int i=head[u];i;i=nxt[i]){
                int v=vv[i];
                if(dis[v]<dis[u]+ww[i]){
                    dis[v]=dis[u]+ww[i];
                    cnt[v]=cnt[u]+1;
                    if(cnt[v]>=n) return 0;
                    if(!inq[v]) inq[v]=1,q.push(v);
                }
            }
        }
        return 1;
    }

    更高效的dfs版spfa判负环

    转载于:https://www.cnblogs.com/santiego/p/11205131.html

    展开全文
  • SPFA板子

    2019-07-23 16:13:00
    #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; const int maxn = 205; vector<pair<int,int>>E[maxn]; int n,m; int d[maxn],inq[maxn];... ...
    #pragma GCC optimize(3)
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 205;
    
    vector<pair<int,int>>E[maxn];
    int n,m;
    
    int d[maxn],inq[maxn];
    void init(){
        for(int i=0;i<maxn;i++) E[i].clear();
        for(int i=0;i<maxn;i++) inq[i] = 0;
        for(int i=0;i<maxn;i++) d[i] = 1e9;
    }
    int main(){
    
        while(cin>>n>>m){
            init();
            for(int i=0;i<m;i++){
                int x,y,z;scanf("%d%d%d",&x,&y,&z);
                E[x].push_back(make_pair(y,z));
                E[y].push_back(make_pair(x,z));
            }
            int s,t;
            scanf("%d%d",&s,&t);
            queue<int> Q;
            Q.push(s),d[s]=0,inq[s]=1;
            while(!Q.empty()){
                int now = Q.front();
                Q.pop();inq[now] = 0;
                for(int i=0;i<E[now].size();i++){
                    int v = E[now][i].first;
                    if(d[v]>d[now]+E[now][i].second){
                        d[v] = d[now]+E[now][i].second;
                        if(inq[v]==1) continue;
                        inq[v]=1;
                        Q.push(v);
                    }
                }
            }
            if(d[t]==1e9) printf("-1\n");
            else printf(d[t]);
        }
        return 0;
    }

     

    展开全文
  • 做ACM最短路问题普遍算法的Floyd-Dijkstra-Spfa板子..
  • 点有2500个,边只有6200个,是稀疏图,于是决定学一下spfa ...spfa板子题,直接上代码了 心得就是稍微学了一下stl() 1 #include<cstdio> 2 #include<cstring> 3 #include<io...

    不存在的惯例放个题目链接https://www.luogu.org/problem/P1339

    点有2500个,边只有6200个,是稀疏图,于是决定学一下spfa

    spfa板子题,直接上代码了

     

    心得就是稍微学了一下stl()

     1 #include<cstdio>
     2 #include<cstring>
     3 #include<iostream>
     4 #include<algorithm>
     5 #include<vector>
     6 #include<queue>
     7 using namespace std;
     8 const int maxn = 2550;
     9 const int INF = 9999999;
    10 struct node{
    11     int v;//终点
    12     int weight;//权值
    13 };
    14 vector<node>mp[maxn];//下标是起点
    15 int dis[maxn],vis[maxn];//dis是起点到下标的长,vis判断是否入队过
    16 void spfa(int src){
    17     int q;
    18     queue<int>Q;
    19     dis[src]=0;
    20     vis[src]=1;
    21     Q.push(src);
    22     while(!Q.empty()){
    23         q=Q.front();
    24         Q.pop();
    25         vis[q]=0;
    26         for(int i=0;i<mp[q].size();i++){
    27             if(dis[q]+mp[q][i].weight<dis[mp[q][i].v]){
    28                 dis[mp[q][i].v]=dis[q]+mp[q][i].weight;
    29                 if(!vis[mp[q][i].v]){
    30                     Q.push(mp[q][i].v);
    31                     vis[mp[q][i].v]=1;
    32                 }
    33             }
    34         }
    35     }
    36     return;
    37 }
    38 
    39 int main(){
    40     int t,c,ts,te;
    41     cin>>t>>c>>ts>>te;
    42     for(int i=1;i<=t;i++)
    43         dis[i]=INF;
    44     while(c--){
    45         int a,b,tmp;
    46         scanf("%d %d %d",&a,&b,&tmp);
    47         mp[a].push_back((node){b,tmp});
    48         mp[b].push_back((node){a,tmp});
    49     }
    50     spfa(ts);
    51     printf("%d\n",dis[te]);
    52     return 0;
    53 }

     

    转载于:https://www.cnblogs.com/yoshinaripb/p/11318270.html

    展开全文
  • } spfa: #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if __...

    题目

    题目链接:https://www.luogu.com.cn/problem/P3371

    代码

    dij:

    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<cstdlib>
    #include<cctype>
    #include<ctime>
    #include<iostream>
    #include<string>
    #include<map>
    #include<queue>
    #include<stack>
    #include<set>
    #include<vector>
    #include<iomanip>
    #include<list>
    #include<bitset>
    #include<sstream>
    #include<fstream>
    #include<complex>
    #include<algorithm>
    #if __cplusplus >= 201103L
    #include <unordered_map>
    #include <unordered_set>
    #endif
    #define ll long long
    #define int long long
    using namespace std;
    const int INF = 0x3f3f3f3f;
    struct sut{
    	int to,val,next;
    }edge[500010]; 
    int head[500010],tot=0;
    void add_edge(int u,int v,int w){
    	edge[++tot].to=v;
    	edge[tot].val=w;
    	edge[tot].next=head[u];
    	head[u]=tot;
    }
    bool vis[500010];
    int dir[500010];int n,m,s;
    void dij(int n1){
    	for(int i=1;i<=m;i++) {
    		dir[i]=(1<<31)-1;
    		vis[i]=0;}
    	priority_queue<pair<int,int>> q;
    	dir[n1]=0;
    	q.push(make_pair(-dir[n1],n1));
    	while(!q.empty()){
    		int u=q.top().second;
    		q.pop();
    		if(vis[u]) continue;
    		vis[u]=1;
    		for(int i=head[u];i;i=edge[i].next){
    			int v=edge[i].to;
    			if(!vis[v]&&dir[v]>dir[u]+edge[i].val){
    				dir[v]=dir[u]+edge[i].val;
    				q.push(make_pair(-dir[v],v));
    			}
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    	cin>>n>>m>>s;
    	for(int i=1;i<=m;i++){
    		int u,v,w;
    		cin>>u>>v>>w;
    		add_edge(u,v,w);
    	//	add_edge(v,u,w);
    	}
    	dij(s);
    	for(int i=1;i<=n;i++){
    		cout<<dir[i]<<" \n"[i==n];
    	}
        return 0;
    }
    
    

    spfa:

    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<cstdlib>
    #include<cctype>
    #include<ctime>
    #include<iostream>
    #include<string>
    #include<map>
    #include<queue>
    #include<stack>
    #include<set>
    #include<vector>
    #include<iomanip>
    #include<list>
    #include<bitset>
    #include<sstream>
    #include<fstream>
    #include<complex>
    #include<algorithm>
    #if __cplusplus >= 201103L
    #include <unordered_map>
    #include <unordered_set>
    #endif
    #define ll long long
    #define int long long
    using namespace std;
    const int INF = 0x3f3f3f3f;
    struct sut{
    	int to,val,next;
    }edge[500010]; 
    int head[500010],tot=0;
    void add_edge(int u,int v,int w){
    	edge[++tot].to=v;
    	edge[tot].val=w;
    	edge[tot].next=head[u];
    	head[u]=tot;
    }
    int dir[500010];int n,m,s;
    bool vis[500010];
    void spfa(int n1){
    	for(int i=1;i<=n;i++){
    		vis[i]=0;
    		dir[i]=(1<<31)-1;
    	}
    	queue<int> q;
    	q.push(n1);
    	vis[n1]=1;
    	dir[n1]=0;
    	while(!q.empty()){
    		int u=q.front();
    		q.pop();
    		vis[u]=0;
    		for(int i=head[u];i;i=edge[i].next){
    			int v=edge[i].to;
    			int d=edge[i].val;
    			if(dir[v]>dir[u]+d){
    				dir[v]=dir[u]+d;
    				if(!vis[v]){
    					vis[v]=1;
    					q.push(v);
    				}
    			}
    		}
    	}
    }
    signed main(){
    	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    	cin>>n>>m>>s;
    	for(int i=1;i<=m;i++){
    		int u,v,w;
    		cin>>u>>v>>w;
    		add_edge(u,v,w);
    	//	add_edge(v,u,w);
    	}
    	spfa(s);
    	for(int i=1;i<=n;i++){
    		cout<<dir[i]<<" \n"[i==n];
    	}
        return 0;
    }
    

    dij spfa 思路区别就不说了,代码上主要的区别是队列里存的东西,还有vis

    展开全文
  • spfa() { // 不就是按照BFS打一波… 23 24 queue< int > q; // 新建队列 25 visited[p_st] = true ; // 源点设为已经访问过了 26 ans_dis[p_st] = 0 ; // 到源点的最短路径为0 27 q.push...
  • spfa.cpp 算法spfa板子

    2020-04-23 14:45:31
    自己打的spfa算法板子。包含邻接表的两种形式,邻接矩阵Map;此代码不完全,(使用是要注释掉部分的)在使用时要结合题意更改。望采纳!
  • SPFA算法板子

    2020-09-22 21:28:47
    } bool SPFA(ll first) { queue<ll>q; q.push(first); while(!q.empty()) { ll now=q.front(); q.pop(); for(ll i=head[now];i>=0;i=edge[i].to) { ll v=edge[i].v; ll w=edge[i].w; if(dis[now]+w[v]) { dis[v]=...
  • spfa优化板子

    2019-10-04 16:04:07
    spfa() { deque < int > Q; for ( int i = 0 ; i ; i++) d[i] = INF; Q.push_front(s); mem(vis, 0 ); d[s] = 0 ; vis[s] = 1 ; while (! Q.empty()) { int u = Q.front(); Q.pop_front(); ...
  • 板子 差分约束spfa,求最长路模板, 以Codeforces 67APartial Teacher为例 多组样例时,应将vis[]数组清空 题目保证无环时,才能使用此代码 否则,最长路应先判断无正环,最短路应先判断无负环 若有对应环,则...
  • $spfa-dfs$优化板子

    2019-05-24 17:58:00
    \(spfa-dfs\)优化板子 快速判断是否存在负环(没负环时不要作死用) bool spfa(int u){ vis[u]=1; for(register int i=head[u];i;i=nxt[i]){ int v=vv[i]; if(dis[v]<dis[u]+ww[i]){ dis[v]=dis[u]+ww...
  • SPFA求最大路

    2019-10-20 00:13:41
    求最长路可以将边权乘以-1,然后求最短路即可,之后...SPFA板子 vector<int>v[MAX_N],w[MAX_N]; int have[MAX_N],dis[MAX_N]; void spfa(int be){ int i; queue<skt>q; skt k; have[be]=true; k.x...
  • spfa算法求最短路的算法步骤: 初始化一个队列,将起点入队。 取出队头元素t,遍历它的所有出边(t, j, w),意思是从t到j,边权为w的边,如果满足dist[j] > dist[t] + w, 就用的dist[t] + w 更新dist[j].同时,如果j...
  • 费用流板子 dij&spfa

    2019-09-24 22:42:15
    (spfa()){ int Min= inf; for ( int i=t;i!=s;i= pre[i]){ // cout[i]; Min= min(flow[id[i]],Min); } for ( int i=t;i!=s;i= pre[i]){ flow[id[i]] -= Min; flow[id[i] ^ 1 ]+= Min; } ans +=...
  • kuangbin板子题题意题目链接floydSPFA 题意 比较明显是一个求负环的板子题 同时这道题floyd也可以勉强过(网上的解法) 题目链接 POJ-3259 floyd #include <cstdio> #include <cmath> #include <...
  • 题意:农场主有N块地编号1到N,有M条路径连接这些边,每条边有一个花费的时间,还有W个单向的虫洞,穿越...SPFA板子即可。BFS版SPFA需要为每个点记录一个入队次数,如果有点入队超过定点数,一定存在负环。 #inclu...
  • spfa

    2018-04-27 22:02:01
    //spfa算法模板(邻接矩阵): //c++ code: void spfa(int s){ for(int i=0; i&lt;=n; i++) dis[i]=99999999; //初始化每点i到s的距离 dis[s]=0; vis[s]=1; q[1]=s; 队列初始化,s为起点 int i, v, head=0, tail...
  • SPFA: #include #include #include #include #include using namespace std; const int maxn=1000+10; const int maxm=5500+10; const int inf=0x3f3f3f3f; struct Edge { int before; int to; int w; }e[maxm]; ...
  • 最大流板子 最小费用最大流 如果你会最大流,那这个基本上可以秒懂。如果你会最大流,那这个基本上可以秒懂。如果你会最大流,那这个基本上可以秒懂。 问题描述\color{Red}问题描述问题描述 给出一个网络图,以及其源点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,443
精华内容 577
关键字:

spfa板子