#include<cstdio>
#include<iostream>
using namespace std;
const int N=10010;
//图的定义
//邻接表
vector<int> Adj[N];//不需要边权时
vector<node>Adj[N];//需要边权时
strcut node
{
int v;//终点编号
int w;//边权
node(int _v,int_w):v(_v),w(_w){}//构造函数
};
Adj[1].push_back(node(3,4));//就能跳过临时变量实现加边操作
//邻接矩阵
int G[N][N];
//图的DFS遍历(邻接表)
int inq[N]={false};
int n;
void DFS(int u,int depth)
{
inq[u]=true;//竟然漏了!!
for(int i=0;i<G[u].size();i++)
{
v=G[u][i];
if(inq[v]==0)
{
DFS(v,depth);
}
}
}
void DFStrave()
{
for(int u=0;u<n;i++)//u==i not int u=G[i];
{
if(inq[u]==0)
DFS(u,1);
}
}
//图的DFS遍历(邻接矩阵)
int inq[N]={false};
int n;
void DFS(int u,int depth)
{
inq[u]=true;//竟然漏了!!
for(int v=0;v<n;v++)
{
if(inq[v]==0&&G[u][v]!=INF)
{
DFS(v,depth);
}
}
}
void DFStrave()
{
for(int u=0;u<n;i++)//u==i not int u=G[i];
{
if(inq[u]==0)
DFS(u,1);
}
}
//图的BFS遍历(邻接表)
int inq[N]={false};
int n;
void BFS(int u,int depth)
{
queue<int> q;
q.push(u);
while(!q.empty())
{
int top=q.front();
printf("%d ",top);
q.pop();
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(inq[v]==0)
{
q.push(v);
inq[v]=true;//竟然漏了!!
}
}
}
}
//图的BFS遍历(邻接矩阵)
int inq[N]={false};
int n;
void BFS(int u,int depth)
{
queue<int> q;
q.push(u);
while(!q.empty())
{
int top=q.front();
printf("%d ",top);
q.pop();
inq[u]=true;//竟然漏了!!
for(int v=0;v<n;v++)
{
if(inq[v]==0&&G[u][v]!=inq)
{
q.push(v);
inq[v]=true;//竟然漏了!!
}
}
}
}
//最短路径
//dijkstra算法
int n;
int G[N][N];
int d[N];
bool vis[N]={false};
int path[N];
//邻接矩阵(例)
void dijkstra(int s)
{
fill(d,d+n,INF);
d[s]=0;
vis[s]=1;
path[s]=-1;
for(int i=0;i<n;i++)
{
int u=-1;
int min=INF;
for(int j=0;j<n;j++)
{
if(min>d[j]&&vis[j]!=0)
{
u=j;
min=d[j];
}
}
if(u=-1) return;
vis[u]=true;
for(int v=0;v<n;v++)
{
if(vis[v]!=0&&G[u][v]!=INF)//只有此处和上面那处和邻接表不同!!
{
if(d[u]+G[u][v]<d[v])
{
d[v]=d[u]+G[u][v];
vis[v]=1;
path[v]=u;//记录前驱结点,会随着的d[v]更新path[v]的!!
num[v]=num[u];//记录关键路径条数,此时path[N]作废
}
else if(d[u]+G[u][v]==d[v])
{
num[v]+=num[u];
}
}
}
}
}
void DFS(int path[],int s,int v)//DFS递归path输出从s开始到v的最短路径上的顶点
{
if(v==s)
{
printf("%d\n",s);
return;
}
DFS(path,s,path[v]);//not DFS(path,s,v-1);
printf("%d\n",v);//从最深处return回来输出除根节点外的所有顶点
}
//SPFA算法
//floyd算法解决全源最短路问题
const int N=200;
int dis[N][N];
fill(dis[0],dis[0]+N*N,INF);//二维数组赋初值
void floyd()
{
for(int k=0;k<n;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(dis[i][k]+dis[k][j]<dis[i][j])&&dis[i][k]!=INF&&dis[k][j]!=INF)//判定是否等于INF防止超限!!
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
//最小生成树
//prim算法
bool vis[N]={false};
int n,G[N][N];
int d[N];//顶点到集合的最短距离
int ans=0;//最小生成树的边权之和
int intprim()//默认从0出发
{
fill(d,d+N,INF);
d[0]=0;
for(int i=0;i<n;i++)
{
int u=-1,min=INF;
for(int j=0;j<n;j++)
{
if(d[j]<min&&vis[d]==0)
{
min=d[j];
u=j;
}
}
if(u==-1) return;
vis[u]=true;
ans+=d[u];
for(int v=0;v<n;v++)
{
if(vis[v]==0&&d[v]>d[u]+G[i][j]&&G[i][j]!=INF)
{
d[v]=d[u]+G[i][j];
}
}
}
return ans;
}
//kruskal算法
struct edge
{
int cost;
int u,v;
}E[N];
bool cmp(edge a,edge b)
{
return a.cost<b.cost;
}
int father[N];
int findfather(int x)
{
if(x==father[x]) return x;
else
{
int f=findfather(father[x]);
father[x]=f;
return f;
}
}
int kruskal(int n,int m)
{
int ans=0;
int Num_Edge=0;//最小生成树边数
for(int i=0;i<n;i++)
{
father[i]=i;
}
sort(E,E+n,cmp);
for(int i=0;i<n;i++)
{
int faU=findfather(E[i].u);
int faV=findfather(E[i].v);
if(faU!=faV)
{
father(faU)=faV;
ans+=E[i].cost;
Num_Edge++;
if(Num_Edge==n-1) break;
}
}
if(Num_Edge!=n-1) return -1;
return ans;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
vector<int> G[N];
int n,m,inDegree[N];
int print[N]={0};
bool topologicalSort()
{
int num=0;
queue<int> q;
for(int i=0;i<n;i++)
{
if(inDegree[i]==0) q.push(i);
}
while(!q.empty())
{
int top=q.front();
print[num++]=top;//开个print数组记录序列
q.pop();
for(int i=0;i<G[top].size();i++)
{
int v=G[top][i];
inDegree[v]--;
if(inDegree[i]==0) q.push(i);
}
}
if(num==n) return true;
return false;
}
#include[HTML_REMOVED]
using namespace std;
int d[N];
int G[N][N];
int ans=0;
int num=0;
int vis[N]={0};
int intprim()//默认从0出发
{
fill(d,d+N,INF);
d[0]=0;
for(int i=0;i[HTML_REMOVED]d[u]+G[u][i]&&G[u][i]!=INF)//别漏了G[u][i]!=INF
{
d[i]=G[u][i];
path[i]=u;
}
}
}
}
return ans;
}