图论学习笔记

Dijkstra单源最短路径

堆优化。注意要定义成小根堆，而priority_queue默认大根堆

再就是每个点最多入队一次，可以用vis数组记录

证明：如果已经出队，说明队列中全都是val值比他大的(负权边?)，这样他的val值一定已经是最终值了；

如果没有入队，进行更改之后会在堆中体现，不需要担心之后还会更新他的val值

#include<bits/stdc++.h>
using namespace std;

const int N=200000,M=1000000,inf=(1<<30)-1+(1<<30);
int n,m,s,cnt;
struct node{
    int num,head,val=inf,vis=0;
    bool operator <(const node &tmp)const{
        return val>tmp.val;//change it into a small root heap
    }
}a[N];
struct edge{
    int nxt,to,len;
}e[M];
priority_queue<node>q;

void add(int u,int v,int w){
    e[++cnt].nxt=a[u].head;
    e[cnt].to=v;
    e[cnt].len=w;
    a[u].head=cnt;
}

void Dij(){
    a[s].val=0;q.push(a[s]);
    while(!q.empty()){
        node x=q.top();q.pop();
        if(a[x.num].vis) continue; a[x.num].vis=1;
        //When it comes to here,x.val is the newest value.It's useless to update once again.
        for(int i=x.head;i;i=e[i].nxt){
            if(e[i].len+x.val<a[e[i].to].val){
                a[e[i].to].val=e[i].len+x.val;
                q.push(a[e[i].to]);
            }
        }
    }
}

int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;++i) a[i].num=i;
    for(int i=1;i<=m;++i){int u,v,w;cin>>u>>v>>w;add(u,v,w);}
    Dij();
    for(int i=1;i<=n;++i) cout<<a[i].val<<' '; cout<<endl;
    return 0;
}

SPFA找负环

vis记录目前已经在队列中的不再次入队，稠密图中效率不如floyd

多测清空！[怒]

#include<bits/stdc++.h>
using namespace std;

const int N=10000,inf=1000000000;
int n,m;
struct node{
	int val,cnt,head,vis;
}nd[N];
queue<int> q;
struct edge{
	int nxt,len,to;
}e[N];int cnt;

void memst(){
	cnt=0;nd[0].val=inf;
	while(!q.empty()) q.pop();
	for(int i=1;i<=n;++i) nd[i]=nd[0];
	for(int j=1;j<=m;++j) e[j]=e[0];
}

void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].len=w;
	e[cnt].nxt=nd[u].head;
	nd[u].head=cnt;
}

int spfa(){
 	++nd[1].cnt;nd[1].val=0; q.push(1);
	while(!q.empty()){
		int x=q.front();q.pop();nd[x].vis=0;
		for(int i=nd[x].head;i;i=e[i].nxt){
			int v=e[i].to;
			if(nd[v].val>nd[x].val+e[i].len){
				nd[v].val=nd[x].val+e[i].len;
				if(nd[v].vis) continue;
				++nd[v].cnt;nd[v].vis=1;
				if(nd[v].cnt>=n) return 1;
				q.push(v);
			}
		}
	}
	return 0;
}

int main(){
	int T;cin>>T;while(T--){
		cin>>n>>m;memst();
		for(int i=1;i<=m;++i){
			int u,v,w;cin>>u>>v>>w;add(u,v,w);
			if(w>=0) add(v,u,w);
		}
		if(spfa()) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}