图论板子
Dijkstra
P4779 【模板】单源最短路径（标准版）
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=2e5+5;
int n,m,s,cnt,hd[N],nxt[M],to[M],w[M],dis[N];
bool vis[N];
struct node{int id,d;node(int a,int b):id(a),d(b){}
};
bool operator <(node a,node b){return a.d>b.d;
}
void add(int a,int b,int c){nxt[++cnt]=hd[a];hd[a]=cnt;to[cnt]=b;w[cnt]=c;
}
void dij(int s){priority_queue<node>q;memset(dis,0x3f,sizeof(dis));dis[s]=0;q.push(node(s,0));while(!q.empty()){node p=q.top();q.pop();if(vis[p.id]) continue;vis[p.id]=true;for(int i=hd[p.id];i;i=nxt[i]){int v=to[i];if(p.d+w[i]<dis[v]){dis[v]=p.d+w[i];q.push(node(v,dis[v]));}}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie();cin>>n>>m>>s;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);}dij(s);for(int i=1;i<=n;i++) cout<<dis[i]<<" ";return 0;
}
Spfa
P3385 【模板】负环
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=2005,M=3005;
int T,n,m,cnt,hd[N],nxt[M<<1],to[M<<1],w[M<<1],dis[N],cnts[N];
bool vis[N];
void add(int a,int b,int c){nxt[++cnt]=hd[a];hd[a]=cnt;to[cnt]=b;w[cnt]=c;
}
bool spfa(){memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));queue<int>q;q.push(1);dis[1]=0;vis[1]=true;while(!q.empty()){int u=q.front();q.pop();vis[u]=false;for(int i=hd[u];i;i=nxt[i]){int v=to[i];if(dis[u]+w[i]<dis[v]){dis[v]=dis[u]+w[i];if(vis[v]) continue;vis[v]=true;if(++cnts[v]>n) return true;q.push(v);}}}return false;
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>T;while(T--){cnt=0;memset(hd,0,sizeof(hd));memset(cnts,0,sizeof(cnts));cin>>n>>m;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);if(c>=0) add(b,a,c);}if(spfa()) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}
Floyd
B3611 【模板】传递闭包
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=105;
int n,f[N][N];
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>f[i][j];}}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){f[i][j]|=f[i][k]&f[k][j];}} } for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<f[i][j]<<" ";}cout<<endl;}return 0;
}
差分约束
P5960 【模板】差分约束
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int n,m,cnt,hd[N],nxt[N<<1],to[N<<1],w[N<<1],dis[N],cnts[N];
bool vis[N];
void add(int a,int b,int c){nxt[++cnt]=hd[a];hd[a]=cnt;to[cnt]=b;w[cnt]=c;
}
void spfa(int s){memset(dis,0x3f,sizeof(dis));dis[s]=0;queue<int>q;q.push(s);vis[s]=true;while(!q.empty()){int u=q.front();q.pop();vis[u]=false;for(int i=hd[u];i;i=nxt[i]){int v=to[i];if(dis[u]+w[i]<dis[v]){dis[v]=dis[u]+w[i];if(vis[v]) continue;vis[v]=true;if(++cnts[v]>n+1){cout<<"NO";exit(0);}q.push(v);}} }
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;add(b,a,c);}for(int i=1;i<=n;i++) add(n+1,i,0);spfa(n+1);for(int i=1;i<=n;i++) cout<<dis[i]<<" ";return 0;
}
同余最短路
P3403 跳楼机
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int cnt,hd[N],nxt[N<<1],to[N<<1];
ll h,x,y,z,w[N<<1],dis[N];
bool vis[N];
struct node{int id;ll d;node(int a,ll b):id(a),d(b){}
};
bool operator <(node a,node b){return a.d>b.d;
}
void add(int a,int b,ll c){nxt[++cnt]=hd[a];hd[a]=cnt;to[cnt]=b;w[cnt]=c;
}
void dij(){priority_queue<node>q;memset(dis,0x3f,sizeof(dis));dis[0]=0;q.push(node(0,0));while(!q.empty()){node p=q.top();q.pop();if(vis[p.id]) continue;vis[p.id]=true;for(int i=hd[p.id];i;i=nxt[i]){int v=to[i];if(p.d+w[i]<dis[v]){dis[v]=p.d+w[i];q.push(node(v,dis[v]));}}}
}
int main(){cin>>h>>x>>y>>z;h--;for(int i=0;i<x;i++){add(i,(i+y)%x,y);add(i,(i+z)%x,z);}dij();ll ans=0;for(int i=0;i<x;i++) if(h>=dis[i]) ans+=(h-dis[i])/x+1;cout<<ans;return 0;
}
Toposort
B3644 【模板】拓扑排序 / 家谱树
#include<bits/stdc++.h>
using namespace std;
const int N=105,M=1e4+5;
int n,m,cnt,hd[N],nxt[M],to[M],w[M],d[N];
void add(int a,int b){nxt[++cnt]=hd[a];hd[a]=cnt;to[cnt]=b;d[b]++;
}
void Toposort(int s){queue<int>q;q.push(s);while(!q.empty()){int u=q.front();q.pop();if(u!=n+1) cout<<u<<" ";for(int i=hd[u];i;i=nxt[i]){int v=to[i];if(--d[v]==0) q.push(v);}}
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){int k;while(1){cin>>k;if(!k) break;add(i,k);}}int S=n+1;for(int i=1;i<=n;i++) if(!d[i]) add(S,i);Toposort(S);return 0;
}
Kruskal
P3366 【模板】最小生成树
#include<bits/stdc++.h>
using namespace std;
const int N=5005,M=2e5+5;
int n,m,f[N],sz[N];
struct edge{int u,v,w;
}e[M];
bool cmp(edge a,edge b){return a.w<b.w;
}
int find(int k){if(f[k]!=k) f[k]=find(f[k]);return f[k];
}
int union1(int a,int b){int fa=find(a),fb=find(b);if(fa==fb) return -1;if(sz[fa]>sz[fb]){sz[fa]+=sz[fb];f[fb]=fa;return sz[fa];}else{sz[fb]+=sz[fa];f[fa]=fb;return sz[fb];}
}
void K(){int res=0;for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;sort(e+1,e+1+m,cmp);for(int i=1;i<=m;i++){int u=e[i].u,v=e[i].v;int z=union1(u,v);if(z==-1) continue;res+=e[i].w;if(z==n){cout<<res;return;}}cout<<"orz";
}
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;K();return 0;
}