本文介绍: dfs可以说是选择一条可行的路径一直走到头，到头之后就是往回走，往回走也有一定的程度，比如往回走了一步，发现又可以往下走了，就继续走。dfs函数写在什么位置，可以这么理解，等于dfs()是一条分界线，他的上边的逻辑我要做什么，修改标志之类的，他的下边就是我做上边的那些没有成功，就要恢复现场排列数字bool st[N];int n;puts(“”);i<=n;i++){if(!st[i]=true;dfs(u+1);
图论总结
搜索
DFS
dfs可以说是选择一条可行的路径一直走到头，到头之后就是往回走，往回走也有一定的程度，比如往回走了一步，发现又可以往下走了，就继续走。dfs函数写在什么位置，可以这么理解，等于dfs()是一条分界线，他的上边的逻辑我要做什么，修改标志之类的，他的下边就是我做上边的那些没有成功，就要恢复现场
排列数字
#include<iostream>
using namespace std;
const int N=11;
int path[N];
bool st[N];
int n;
void dfs(int u){
if(u==n){
for(int i=0;i<n;i++) printf("%d ",path[i]);
puts("");
}
for(int i=1;i<=n;i++){
if(!st[i]){
path[u]=i;
st[i]=true;
dfs(u+1);
st[i]=false;
}
}
}
int main(){
scanf("%d",&n);
dfs(0);
}
n皇后问题
#include<iostream>
using namespace std;
const int N=11,M=22;
char q[N][N];
bool col[M],dg[M],udg[M];
int n;
void dfs(int u){
if(u==n){
for(int i=0;i<n;i++) puts(q[i]);
puts("");
}
for(int i=0;i<n;i++){
if(!col[i] && !dg[u+i] && !udg[u+n-i]){
q[u][i]='Q';
col[i]=dg[u+i]=udg[u+n-i]=true;
dfs(u+1);
col[i]=dg[u+i]=udg[u+n-i]=false;
q[u][i]='.';
}
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
q[i][j]='.';
dfs(0);
}
BFS
BFS就是一层一层往下走，如果符合条件就把他装入队列中，并且维护一些东西，然后每次也是取队头元素进行下一步操作
走迷宫(经典例题)
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int g[N][N],d[N][N];
int n,m;
PII q[N*N];
void bfs(){
int hh=0,tt=-1;
memset(d,-1,sizeof d);
d[0][0]=0;
q[++tt] = {0,0};
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
while(hh<=tt){
PII t=q[hh++];
for(int i=0;i<4;i++){
int x=t.first+dx[i],y=t.second+dy[i];
if(x>=0 && x<n && y>=0 && y<m && !g[x][y] && d[x][y]==-1){
d[x][y]=d[t.first][t.second]+1;
q[++tt] = {x,y};
}
}
}
printf("%d",d[n-1][m-1]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
scanf("%d",&g[i][j]);
}
bfs();
}
树与图的深度优先遍历
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int h[N],e[N*2],ne[N*2],idx;
bool st[N];
int n;
int ans = N;
void add(int a,int b){
e[idx] = b;
ne[idx]=h[a];
h[a]=idx++;
}
int dfs(int u){
st[u]=true;
int sum=1,res=0;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]){
int s=dfs(j);
sum += s;
res=max(res,s);
}
}
res=max(res,n-sum);
ans=min(res,ans);
return sum;
}
int main(){
scanf("%d",&n);
memset(h,-1,sizeof h);
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
dfs(1);
printf("%d",ans);
}
树与图的广度优先遍历
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
void bfs(){
int hh=0,tt=-1;
q[++tt] = 1;
memset(d,-1,sizeof d);
d[1]=0;
while(hh<=tt){
int t=q[hh++];
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(d[j]==-1){
d[j]=d[t]+1;
q[++tt] = j;
}
}
}
printf("%d",d[n]);
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
bfs();
}
有向图的拓扑序列
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int h[N],e[N],ne[N],idx;
int d[N];
int n,m;
int q[N];
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool topsort(){
int hh=0,tt=-1;
for(int i=1;i<=n;i++){
if(!d[i]) q[++tt] = i;
}
while(hh<=tt){
int t=q[hh++];
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(--d[j]==0){
q[++tt] = j;
}
}
}
return tt==n-1;
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
d[b]++;
}
if(topsort()){
for(int i=0;i<n;i++) printf("%d ",q[i]);
}
else puts("-1");
}
Dijkstra算法求解最短路问题
#include<iostream>
#include<cstring>
using namespace std;
const int N=510;
int g[N][N];
int dist[N];
bool st[N];
int n,m;
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j] && (t==-1 || dist[t]>dist[j]))
t=j;
}
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],dist[t]+g[t][j]);
st[t]=true;
}
return dist[n];
}
int main(){
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b]=min(g[a][b],c);
}
int t=dijkstra();
if(t==0x3f3f3f3f) puts("-1");
else printf("%d",t);
}
Dijkstra算法求解最短路问题(小根堆优化)
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=100010,M=200010;
typedef pair<int,int> PII;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
int n,m;
void add(int a,int b,int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++;
}
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,1});
while(heap.size()){
PII t=heap.top();
heap.pop();
int ver=t.second;
if(st[ver]) continue;
st[ver] = true;
for(int i=h[ver];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[ver]+w[i]){
dist[j]=dist[ver]+w[i];
heap.push({dist[j],j});
}
}
}
return dist[n];
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
int t=dijkstra();
if(t==0x3f3f3f3f) puts("-1");
else printf("%d",t);
}
bellman-ford算法求解有负边的最短路
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int dist[N],last[N];
struct Edge{
int a,b,c;
}edges[M];
int bellman_ford(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++){
memcpy(last,dist,sizeof dist);
for(int j=0;j<m;j++){
Edge e=edges[j];
dist[e.b]=min(dist[e.b],last[e.a]+e.c);
}
}
return dist[n];
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edges[i]={a,b,c};
}
int t=bellman_ford();
if(t>0x3f3f3f3f/2) puts("impossible");
else printf("%d",t);
}
spfa算法
spfa求解最短路
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int h[N],e[N*2],w[N*2],ne[N*2],idx;
int dist[N],q[N];
bool st[N];
int n,m;
void add(int a,int b,int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int spfa(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
int hh=0,tt=-1;
q[++tt] = 1;
while(hh<=tt){
int t=q[hh++];
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
if(!st[j]){
st[j]=true;
q[++tt] = j;
}
}
}
}
return dist[n];
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
int t=spfa();
if(t==0x3f3f3f3f) puts("impossible");
else printf("%d",t);
}
spfa求负环
#include<iostream>
#include<cstring>
using namespace std;
const int N=2010,M=10010;
int h[N],e[M],w[M],ne[M],idx;
int dist[N],q[N*M],cnt[N];
bool st[N];
int n,m;
void add(int a,int b,int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
bool spfa(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
int hh=0,tt=-1;
for(int i=1;i<=n;i++){
q[++tt] = i;
}
while(hh<=tt){
int t=q[hh++];
st[t]=false;
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
cnt[j]=cnt[t]+1;
if(cnt[j]>=n) return true;
if(!st[j]){
st[j]=true;
q[++tt] = j;
}
}
}
}
return false;
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
if(spfa()) puts("Yes");
else puts("No");
}
floyd求解多源最短路
#include<iostream>
using namespace std;
const int N=210,INF=1e9;
int d[N][N];
int n,m,q;
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) d[i][j]=0;
else d[i][j]=INF;
}
}
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
d[a][b]=min(d[a][b],c);
}
floyd();
while(q--){
int a,b;
scanf("%d%d",&a,&b);
if(d[a][b]> INF/2 ) puts("impossible");
else printf("%dn",d[a][b]);
}
}
prim算法求解最短生成树
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int g[N][N];
int dist[N];
bool st[N];
int n,m;
int prim(){
memset(dist,0x3f,sizeof dist);
int res=0;
for(int i=0;i<n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j] && (t==-1 || dist[t]>dist[j]))
t=j;
}
if(i && dist[t]==INF) return INF;
if(i) res += dist[t];
for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
st[t]=true;
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b]=g[b][a]=min(g[a][b],c);
}
int t=prim();
if(t==INF) puts("impossible");
else printf("%d",t);
}
kruskal算法求解最小生成树
kruskal算法其中就有一些并查集的思想，把边从权值小的往大的找，当连通了之后就停止，也就是他们的父节点相同。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010,M=200010,INF=0x3f3f3f3f;
int p[N];
struct Edge{
int a,b,w;
}edges[M];
int res,cnt;
int n,m;
bool cmp(struct Edge a,struct Edge b){
return a.w<b.w;
}
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int kruskal(){
sort(edges,edges+m,cmp);
for(int i=0;i<m;i++){
int a=edges[i].a,b=edges[i].b,w=edges[i].w;
a=find(a),b=find(b);
if(a!=b){
p[a]=b;
res += w;
cnt++;
}
}
return cnt<n-1 ? INF : res;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edges[i]={a,b,c};
}
for(int i=1;i<=n;i++) p[i]=i;
int t=kruskal();
if(t==INF) puts("impossible");
else printf("%d",t);
}
染色法判定二分图
**总体思想：**二分图就是分成两边，然后一边染一个色，如果最后的出现重复染色的情况（即染色冲突），就不是二分图
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010,M=200010;
int h[N],e[M],ne[M],idx;
int color[N];
int n,m;
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
bool dfs(int u,int c){
color[u]=c;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!color[j]){
if(!dfs(j,3-c)) return false;
}else if(color[j]==c) return false;
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
bool flag=true;
for(int i=1;i<=n;i++){
if(!color[i]){
if(!dfs(i,1)){
flag=false;
break;
}
}
}
if(flag) puts("Yes");
else puts("No");
}
匈牙利算法求解二分图最大匹配
#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=100010;
int h[N],e[M],ne[M],idx;
bool st[N];
int n1,n2,m;
int match[N];
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
bool find(int u){
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]){
st[j]=true;
if(!match[j] || find(match[j])){
match[j]=u;
return true;
}
}
}
return false;
}
int main(){
scanf("%d%d%d",&n1,&n2,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
int res=0;
for(int i=1;i<=n1;i++){
memset(st,false,sizeof st);
if(find(i)) res++;
}
printf("%d",res);
}
原文地址:https://blog.csdn.net/zyang654321/article/details/134700334
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_7935.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
