# 复习1-图论模板

## 1.最短路

```void spfa(){
queue<int> q;
for(int i = 1;i <= n;i++) d[i] = 0x7fffffff;
q.push(s);vis[s] = 1;d[s] = 0;
while(!q.empty()){
int x = q.front();q.pop();vis[x] = 0;
for(int i = head[x];i;i = G[i].pre){
int v = G[i].to,w = G[i].v;
if(d[v] > d[x] + w){
d[v] = d[x] + w;
if(!vis[v]){
vis[v] = 1;
q.push(v);
}
}
}
}
}```

SPFA

```struct HeapNode{
int u,d;
bool operator < (const HeapNode& rhs) const{
return d > rhs.d;
}
};

void Dijkstra()
{
priority_queue<HeapNode> q;
for(int i = 1;i <= n;i++)
d[i] = INF;
d[s] = 0;
q.push((HeapNode){s,d[s]});
while(!q.empty()){
HeapNode x = q.top();q.pop();
int u = x.u;
if(x.d > d[u]) continue;
for(register int i = last[u];i >= 0;i = e[i].next)
{
int v = e[i].v,w = e[i].w;
if(d[u] + w < d[v]){
d[v] = d[u] + w;
q.push((HeapNode){v,d[v]});
}
}
}
}```

Dijkstra+堆优化

```/*
Bellman-Ford算法 题解上的
*/

#include<iostream>
using namespace std;
const int maxx=10001;
int n,m,s,dis[maxx],w[500001],num[maxx],f[maxx][maxx/10][2],a=0;
int main(){
ios::sync_with_stdio(false);
cin>>n>>m>>s;
for(int i=1;i<=n;i++) dis[i]=400;
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++) w[i]=400;
for(int i=1;i<=m;i++){
int x,y,v;
cin>>x>>y>>v;
f[x][++num[x]][0]=y;
f[x][num[x]][1]=i;
w[i]=v;
}
dis[s]=0;
while(a<=50){ //循环大法好
for(int i=1;i<=n;i++)
for(int j=1;j<=num[i];j++)
dis[f[i][j][0]]=min(dis[f[i][j][0]],dis[i]+w[f[i][j][1]]);
a++;
}
for(int i=1;i<=n;i++) if(dis[i]==400) cout<<2147483647<<‘ ‘; else cout<<dis[i]<<‘ ‘;
return 0;
}```

Bellman-Ford

## 2.最小生成树

```/*
适用于稀疏图
*/
#include <bits/stdc++.h>

using namespace std;

int p[5005];
int n,m,num = 0;

struct node
{
int x,y,z;
}e[200005];

int cmp(node a,node b)
{
return a.z < b.z;
}

int find(int x)
{
return p[x] == x ? x : p[x] = find(p[x]);
}

int Kruskal()
{
for(int i = 1;i <= n;i++) p[i] = i;
sort(e+1,e+m+1,cmp);
int ans = 0,cnt = 0;
for(int i = 1;i <= m;i++)
{
int x = find(e[i].x);
int y = find(e[i].y);
if(x != y)
{
p[x] = y;
ans += e[i].z;
cnt++;
}
if(cnt == n-1) break;
}
return ans;
}

int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= m;i++)
{
scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
}
printf("%d\n",Kruskal());
return 0;
}```

Kruskal算法

```/*
适用于稠密图（然而没啥用）
*/

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5010;
const int INF = 0x7fffffff;

struct node{
int to,v,pre;
}e[400010];

e[cnt].to=to;
e[cnt].v=v;
}

int Prim(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;int ans = 0;
for(int i = 1;i <= n;i++){
int minn = INF,k = 0;
for(int j = 1;j <= n;j++){
if(!vis[j] && dis[j] < minn){
minn = dis[j];
k = j;
}
}
if(minn == INF)break;
vis[k] = 1;
for(int j = head[k];j;j = e[j].pre){
int f = e[j].to;
if(!vis[f])
dis[f] = min(dis[f],e[j].v);
}
}
for(int i = 1;i <= n;i++) ans += dis[i];
return ans;
}

int main(){
scanf("%d%d",&n,&m);
int x,y,z;
for(int i = 1;i <= m;i++){
scanf("%d%d%d",&x,&y,&z);
}
printf("%d\n",Prim());
return 0;
}```

Prim算法

## 3.LCA

```/*
倍增写法 常数略大
我觉得不太好理解 所以我不用倍增了
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500010;

int n,m,s;

struct node{
int to,pre;
}G[MAXN*2];

G[++cnt].to = to;
}

int x = 0,m = 1;
char ch;
while(ch < ‘0‘ || ch > ‘9‘)  {if(ch == ‘-‘) m = -1;ch = getchar();}
while(ch >= ‘0‘ && ch <= ‘9‘){x = x*10+ch-‘0‘;ch=getchar();}
return m * x;
}

inline void dfs(int u)
{
for(int i = head[u];i;i = G[i].pre)
{
int v = G[i].to;
if(v != f[u][0])
{
f[v][0] = u;
deep[v] = deep[u] + 1;
dfs(v);
}
}
}

inline int lca(int u,int v)
{
if(deep[u] < deep[v]) swap(u,v);
int dis = deep[u] - deep[v];
for(register int i = 0;i <= lg[n];i++)
{
if((1 << i) & dis) u = f[u][i];
}
if(u == v) return u;
for(register int i = lg[deep[u]];i >= 0;i--)
{
if(f[u][i] != f[v][i])
{
u = f[u][i];v = f[v][i];
}
}
return f[u][0];
}

inline void init()
{
for(register int j = 1;j <= lg[n];j++)
{
for(register int i = 1;i <= n;i++)
{
if(f[i][j-1] != -1)
f[i][j] = f[f[i][j-1]][j-1];
}
}
}

int main()
{
int x,y,a,b;
for(register int i = 1;i <= n;i++)
{
lg[i] = lg[i-1] + (1 << lg[i-1] + 1 == i);
}
for(register int i = 1;i <= n-1;i++)
{
}
dfs(s);
init();
while(m--)
{
printf("%d\n",lca(a,b));
}
return 0;
}```

```/*
这种树剖写法好理解（好背）
虽然代码比倍增略长 但是也比倍增快
简直完美2333333
所以以后就用这种方法辣
*/

#include <bits/stdc++.h>

using namespace std;

const int maxn = 500005;

int fa[maxn],top[maxn],id[maxn],son[maxn],depth[maxn],size[maxn];//树剖要用的所有数组

struct node{
int to,pre;
}G[maxn*2];

G[++cnt].to = to;
}

void dfs1(int x){
size[x] = 1;
for(int i = head[x];i;i = G[i].pre){
int cur = G[i].to;
if(cur == fa[x]) continue;
depth[cur] = depth[x] + 1;
fa[cur] = x;
dfs1(cur);
size[x] += size[cur];
if(size[cur] > size[son[x]]) son[x] = cur;
}
}

void dfs2(int x,int t){
top[x] = t;
if(son[x]) dfs2(son[x],t);
for(int i = head[x];i;i = G[i].pre){
int cur = G[i].to;
if(cur != fa[x] && cur != son[x])
dfs2(cur,cur);
}
}

int lca(int x,int y){
while(top[x] != top[y]){
if(depth[top[x]] < depth[top[y]]) swap(x,y);
x = fa[top[x]];
}
if(depth[x] > depth[y]) swap(x,y);
return x;
}

int main(){
int x,y,a,b;
scanf("%d%d%d",&n,&m,&s);
for(int i = 1;i < n;i++){
scanf("%d%d",&x,&y);
}
dfs1(s);
dfs2(s,s);
while(m--){
scanf("%d%d",&a,&b);
printf("%d\n",lca(a,b));
}
return 0;
}```

```/*
Tarjan算法（题解） 常数挺大的，不推荐，容易被卡
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <cstring>
#include <queue>
#include <map>
#define ll long long
#define ri register int
#define ull unsigned long long
using namespace std;
const int maxn=500005;
const int inf=0x7fffffff;
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c==‘-‘;
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
int n,m,s,t;
struct Edge{
int ne,to;
}edge[maxn<<1];
struct QU{
int d,id;
QU(int x,int y){d=x,id=y;}
QU(){;}
};
vector <QU>q[maxn];
int h[maxn],num_edge=0,ans[maxn];
edge[++num_edge].ne=h[f];
edge[num_edge].to=to;
h[f]=num_edge;
return;
}
int fa[maxn],vis[maxn];
int get(int x){
if(fa[x]!=x)fa[x]=get(fa[x]);
return fa[x];
}
void dfs(int cur){
int u,v;
vis[cur]=1;
for(ri i=h[cur];i;i=edge[i].ne){
v=edge[i].to;
if(vis[v])continue;
dfs(v);
fa[v]=cur;//dfs后再合并
}
for(ri i=0;i<q[cur].size();i++){
u=q[cur][i].d,v=q[cur][i].id;
if(vis[u]==2){
ans[v]=get(u);
}
}
vis[cur]=2;//dfs过
return ;
}
int main(){
int x,y;
for(ri i=1;i<n;i++){
fa[i]=i;
}fa[n]=n;
for(ri i=1;i<=m;i++){
//q[x].push_back(y);q[y].push_back(x);
q[x].push_back(QU(y,i));
q[y].push_back(QU(x,i));
}
dfs(s);
for(ri i=1;i<=m;i++){
printf("%d\n",ans[i]);
}
return 0;
}```

Tarjan

## 4.二分图最大匹配

```#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3+5;

vector<int> G[maxn];

bool dfs(int x){
for(int i = 0;i < G[x].size();i++){
int v = G[x][i];
if(!vis[v]){
vis[v] = 1;
}
}
}
return false;
}

int main()
{
int x,y;
scanf("%d%d%d",&n,&m,&e);
for(int i = 1;i <= e;i++){
scanf("%d%d",&x,&y);
if(x <= n && y <= m) G[x].push_back(y);
}
int ans = 0;
for(int i = 1;i <= n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
printf("%d\n",ans);
return 0;
}```

## 5.Tarjan

```vector<int> G[maxn];  //vector邻接表存图
int pre[maxn],low[maxn],sccno[maxn],cnt,scccnt;
//pre[v]值，sccno[i]就是i所在的强连通分量的编号，dfs_clock表示第几次dfs，
//scc_cnt表示找到的强连通分量序号的临时值
stack<int> S;//存储dfs到的每一个点

void dfs(int u)
{
S.push(u);
for(int i = 0;i < G[u].size();i++)//遍历与点u相连的所有点
{
int v = G[u][i];//取点
if(!pre[v]){//如果点v没有遍历过
dfs(v);//深搜
} else if(!sccno[v])//此时v已经搜过，但是不属于任何一个scc，那么就说明已经形成了环
{
low[u] = min(low[u],pre[v]);
}
}
if(low[u] == pre[u]){//如果u为最先搜到的点，它就是这个scc的根节点
scccnt++;
for(;;)
{
int x = S.top();S.pop();//取一个搜过的点
sccno[x] = scccnt;//它属于这个强联通分量
if(x == u) break;//直到栈中
}
}
}

void find_scc(int n)
{
cnt = scccnt = 0;
memset(sccno,0,sizeof(sccno));
memset(pre,0,sizeof(pre));
for(int i = 1;i <= n;i++)
if(!pre[i]) dfs(i);
}```

```/*
易得出状态转移为val[v] = max(val[v],val[pre] + a[v])
于是通过tarjan算法把所有环缩为一点,跑一遍DAG上的DP即可
*/
#include <bits/stdc++.h>

using namespace std;

const int maxn = 10e5+5;

int scc[maxn],dfn[maxn],low[maxn],stac[maxn];
int val[maxn],cnt,cnt1,scc_clock,top,n,m,tot,scc_amount;

struct node{
int to,from,pre;
}g1[maxn*2],g2[maxn*2];//g1为原来的图，g2为缩点后的图

g1[++cnt].from = from;
g1[cnt].to = to;

g2[++cnt1].from = from;
g2[cnt1].to = to;

void tarjan(int x){
low[x] = dfn[x] = ++scc_clock;//初始化为时间戳
stac[++top] = x;vis[x] = 1;//入栈、标志数组设为1
for(register int i = head1[x];i;i = g1[i].pre){//遍历与x连接的点
int v = g1[i].to;
if(!dfn[v]){
tarjan(v);
low[x] = min(low[x],low[v]);
}else if(vis[v]){
low[x] = min(low[x],dfn[v]);
}
}//一顿tarjan的操作
if(low[x] == dfn[x]){
scc_amount++;
int y;
while(y = stac[top--]){//出栈
scc[y] = x;
vis[y] = 0;//我也不知道为啥
if(x == y) break;
a[x] += a[y];//加权值
}
}
}

int dfs(int u){
val[u] = a[u];
for(int i = head2[u];i;i = g2[i].pre){
int v = g2[i].to;
dfs(v);
val[v] = max(val[v],val[u] + a[v]);
}
}

int main(){
int x,y;
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;i++){
scanf("%d",a+i);
}
for(register int i = 1;i <= m;i++){
scanf("%d%d",&x,&y);
}
for(register int i = 1;i <= n;i++){
if(!dfn[i]) tarjan(i);//tarjan算法基本操作
}
for(register int i = 1;i <= m;i++){
x = scc[g1[i].from],y = scc[g1[i].to];
if(x != y){//如果不属于同一强连通分量，就连边
}
}
int ans = 0;
for(int i = 1;i <= scc_amount;i++){
if(!val[i]){
dfs(i);
ans = max(ans,val[i]);
}
}
printf("%d\n",ans);
return 0;
}```

```/*

*/
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;

int low[maxn],dfn[maxn],cut[maxn];
int n,m,cnt;
vector<int> G[maxn];

void tarjan(int x,int father){
int child = 0;
low[x] = dfn[x] = ++cnt;
for(int i = 0;i < G[x].size();i++){
int v = G[x][i];
if(!dfn[v]){
tarjan(v,father);
low[x] = min(low[x],low[v]);
if(dfn[x] <= low[v] && x != father) cut[x] = 1;
if(x == father) child++;
}
low[x] = min(low[x],dfn[v]);
}
if(x == father && child >= 2) cut[x] = 1;
}

int main(){
int x,y;
scanf("%d%d",&n,&m);
for(int i = 1;i <= m;i++){
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
int ans = 0;
for(int i = 1;i <= n;i++) if(!dfn[i]) tarjan(i,i);
for(int i = 1;i <= n;i++){
if(cut[i]) ans++;
}
printf("%d\n",ans);
for(int i = 1;i <= n;i++){
if(cut[i]) printf("%d ",i);
}
return 0;
}```

## C++智能指针模板类复习

//C++智能指针模板类复习 #include<iostream> #include<memory> using namespace std; //智能指针用于确保程序不存在内存和资源泄漏且是异常安全的. //C++98中提供了auto_ptr,C++11摒弃了auto_ptr,并提出了unique_ptr .shared_ptr.weak_ptr void show1() { int* p = new int(4); cout << *p << endl;