当前位置:网站首页>2/10 parallel search set +bfs+dfs+ shortest path +spfa queue optimization
2/10 parallel search set +bfs+dfs+ shortest path +spfa queue optimization
2022-07-06 04:03:00 【Zhong Zhongzhong】
Made a good question :
The longest path + Chain forward star +spfa
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;
int head[maxn],d,p,c,f,s,cnt,pp[maxn],dis[maxn];
bool vis[maxn],flag;
struct node
{
int to,dis,nxt;
}e[maxn];
void add_edge(int from,int to,int w)
{
e[++cnt].to=to;
e[cnt].dis=w;
e[cnt].nxt=head[from];
head[from]=cnt;
}
queue<int>q;
void spfa()
{
dis[s]=d;
q.push(s);
vis[s]=1;
pp[s]++;
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=0;
if(++pp[u]>c)
{
printf("-1\n");
flag=1;
return;
}
for(int i=head[u];~i;i=e[i].nxt)
{
int v=e[i].to;
if(dis[v]<dis[u]+e[i].dis)
{
dis[v]=dis[u]+e[i].dis;
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
}
int main()
{
scanf("%d%d%d%d%d",&d,&p,&c,&f,&s);
head[0]=-1;
for(int i=1;i<=c;i++)
head[i]=-1;
for(int i=1;i<=p;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v,d);
}
for(int i=1;i<=f;i++)
{
int u,v,w;scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,d-w);
}
spfa();
if(flag)
return 0;
int tmp=0;
for(int i=1;i<=c;i++)
{
tmp=max(tmp,dis[i]);
}
cout<<tmp<<endl;
return 0;
}
https://www.luogu.com.cn/problem/P4826
A maximum spanning tree problem , I don't understand the explanation . The key is the following processing , The object of joint search is undirected edge , Therefore, there is no need to build edges in both directions like the shortest path .
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(i!=j)
add_edge(i,j,a[i]^a[j]);
}
}
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=5e6+5;
int n,m,a[2005],f[2005],minn=inf,cnt,g;
struct node
{
int l,r,w;
}e[maxn];
void add_edge(int from,int to,int w)
{
e[++cnt].l=from;
e[cnt].r=to;
e[cnt].w=w;
}
bool cmp(node e1,node e2)
{
return e1.w>e2.w;
}
int r_find(int r)
{
while(r==f[r])
return r;
return f[r]=r_find(f[r]);
}
void kruskal()
{
long long sum=0;
for(int i=1;i<=cnt;i++)
{
int fx=r_find(e[i].l),fy=r_find(e[i].r);
if(fx==fy)
continue;
g++;
f[fx]=fy;
sum+=e[i].w;
if(g==n-1)
break;
}
cout<<sum<<endl;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(i!=j)
add_edge(i,j,a[i]^a[j]);
}
}
sort(e+1,e+cnt+1,cmp);
kruskal();
return 0;
}
2.bfs
mp Record the points on the chart and arrive in several steps
f[100005][3]: Look for the a,b Data range of , Here is how many points exist
bool vis[maxn][maxn]: Judge whether this point has passed , There's a caveat , Reaching this point first means that it takes the least time
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=5050;
int mp[maxn][maxn],f[100005][3],n,m,a,b;
bool vis[maxn][maxn];
int dx[4]={
1,-1,0,0};
int dy[4]={
0,0,-1,1};
struct node
{
int x,y,step;
};
queue<node>q;
void tag(int x,int y)
{
node cur;
cur.x=x;
cur.y=y;cur.step=0;
q.push(cur);
vis[x][y]=1;
return;
}
void bfs()
{
node cur,nxt;
while(!q.empty()) // Not empty return 0
{
cur=q.front();
mp[cur.x][cur.y]=cur.step;
q.pop();
for(int i=0;i<4;i++)
{
int x=cur.x+dx[i];
int y=cur.y+dy[i];
if(x>=1&&x<=n&&y>=1&&y<=n&&!vis[x][y])
{
vis[x][y]=1;
nxt.x=x;nxt.y=y;
nxt.step=cur.step+1;
q.push(nxt);
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&a,&b);
for(int i=1;i<=a;i++)
{
int x,y;scanf("%d%d",&x,&y);
tag(x,y);
}
for(int i=1;i<=b;i++)
{
scanf("%d%d",&f[i][1],&f[i][2]);
}
bfs();
for(int i=1;i<=b;i++)
{
printf("%d\n",mp[f[i][1]][f[i][2]]);
}
return 0;
}
3.https://www.luogu.com.cn/problem/P2196
A very classic deep search topic .
From the transformation of state :
If there is a road connected with the current floor and it has not been visited , It means that you can always dig down ;
When the digging goes on , Just record the path , Sum maximum , Go back ;
The importance of backtracking is needless to say
#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=50;
int a[maxn],f[maxn][maxn],n,m,b,path[maxn],tmp,ans[maxn],gg;
bool vis[maxn];
int check(int x)
{
for(int i=1;i<=n;i++)
{
if(f[x][i]&&!vis[i]) // It can also dig down and return 1
return 1;
}
return 0; // I can't dig any more and return 0
}
void dfs(int x,int step,int sum)
{
if(!check(x))
{
if(tmp<sum)
{
tmp=sum;gg=step;
for(int i=1;i<=step;i++)
ans[i]=path[i];
}
return;
}
for(int i=1;i<=n;i++)
{
if(f[x][i]&&!vis[i])
{
vis[i]=1;
path[step+1]=i;
dfs(i,step+1,sum+a[i]);
vis[i]=0;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int x;scanf("%d",&x);
f[i][j]=x;
}
}
for(int i=1;i<=n;i++)
{
path[1]=i;
vis[i]=1;
dfs(i,1,a[i]);
vis[i]=0;
}
for(int i=1;i<=gg;i++)
{
cout<<ans[i]<<" ";
}
cout<<endl;
cout<<tmp<<endl;
return 0;
}
Graph storage of chained forward stars + Deep search
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
struct node
{
int to,dis,nxt;
}e[maxn];
int head[maxn],f[maxn],n,m,cnt;
bool vis[maxn];
void add_edge(int from,int to,int dis)
{
e[++cnt].to=to;
e[cnt].dis=dis;
e[cnt].nxt=head[from];
head[from]=cnt;
}
void dfs(int x,int val)
{
f[x]=val;
vis[x]=1;
for(int i=head[x];~i;i=e[i].nxt)
{
if(!vis[e[i].to])
dfs(e[i].to,val^e[i].dis);
}
}
int main()
{
scanf("%d",&n);
head[0]=-1;
for(int i=1;i<=n;i++)
head[i]=-1;
for(int i=1;i<=n-1;i++)
{
int u,v,w;scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);add_edge(v,u,w);
}
dfs(1,0);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
cout<<(f[x]^f[y])<<endl;
}
return 0;
}
边栏推荐
- Stack and queue
- Record an excel xxE vulnerability
- 3分钟带你了解微信小程序开发
- 判断当天是当月的第几周
- Cf603e pastoral oddities [CDQ divide and conquer, revocable and search set]
- MySQL reads missing data from a table in a continuous period of time
- MySql數據庫root賬戶無法遠程登陸解决辦法
- The Research Report "2022 RPA supplier strength matrix analysis of China's banking industry" was officially launched
- STC8H开发(十二): I2C驱动AT24C08,AT24C32系列EEPROM存储
- Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts
猜你喜欢
Record the pit of NETCORE's memory surge
In Net 6 CS more concise method
简易博客系统
Microkernel structure understanding
P7735-[noi2021] heavy and heavy edges [tree chain dissection, line segment tree]
MySql数据库root账户无法远程登陆解决办法
Stack and queue
【按鍵消抖】基於FPGA的按鍵消抖模塊開發
Do you know cookies, sessions, tokens?
Développement d'un module d'élimination des bavardages à clé basé sur la FPGA
随机推荐
[introduction to Django] 11 web page associated MySQL single field table (add, modify, delete)
Microkernel structure understanding
WPF effect Article 191 box selection listbox
/usr/bin/gzip: 1: ELF: not found/usr/bin/gzip: 3: : not found/usr/bin/gzip: 4: Syntax error:
mysql关于自增长增长问题
Le compte racine de la base de données MySQL ne peut pas se connecter à distance à la solution
Serial port-rs232-rs485-ttl
How does technology have the ability to solve problems perfectly
[Massey] Massey font format and typesetting requirements
Facebook等大廠超十億用戶數據遭泄露,早該關注DID了
C form application of C (27)
Determine which week of the month the day is
Ks003 mall system based on JSP and Servlet
Error 1045 (28000): access denied for user 'root' @ 'localhost' (using password: no/yes
Use js to complete an LRU cache
登录mysql输入密码时报错,ERROR 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: NO/YES
In Net 6 CS more concise method
/usr/bin/gzip: 1: ELF: not found/usr/bin/gzip: 3: : not found/usr/bin/gzip: 4: Syntax error:
潘多拉 IOT 开发板学习(HAL 库)—— 实验9 PWM输出实验(学习笔记)
An article will give you a comprehensive understanding of the internal and external components of "computer"