当前位置:网站首页>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;
}
边栏推荐
- Web components series (VII) -- life cycle of custom components
- The global and Chinese market of negative pressure wound therapy unit (npwtu) 2022-2028: Research Report on technology, participants, trends, market size and share
- Class A, B, C networks and subnet masks in IPv4
- math_ Derivative function derivation of limit & differential & derivative & derivative / logarithmic function (derivative definition limit method) / derivative formula derivation of exponential functi
- 登录mysql输入密码时报错,ERROR 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: NO/YES
- User perceived monitoring experience
- mysql从一个连续时间段的表中读取缺少数据
- 【可调延时网络】基于FPGA的可调延时网络系统verilog开发
- Cf603e pastoral oddities [CDQ divide and conquer, revocable and search set]
- [adjustable delay network] development of FPGA based adjustable delay network system Verilog
猜你喜欢
Stack and queue
如何修改表中的字段约束条件(类型,default, null等)
C#(二十八)之C#鼠标事件、键盘事件
User experience index system
[introduction to Django] 11 web page associated MySQL single field table (add, modify, delete)
Flask learning and project practice 9: WTF form verification
What is the difference between gateway address and IP address in tcp/ip protocol?
Développement d'un module d'élimination des bavardages à clé basé sur la FPGA
[optimization model] Monte Carlo method of optimization calculation
DM8 backup set deletion
随机推荐
P7735-[noi2021] heavy and heavy edges [tree chain dissection, line segment tree]
/usr/bin/gzip: 1: ELF: not found/usr/bin/gzip: 3: : not found/usr/bin/gzip: 4: Syntax error:
MySQL master-slave replication
[Key shake elimination] development of key shake elimination module based on FPGA
MySql数据库root账户无法远程登陆解决办法
Ipv4中的A 、B、C类网络及子网掩码
JVM的手术刀式剖析——一文带你窥探JVM的秘密
Align items and align content in flex layout
在 .NET 6 中使用 Startup.cs 更简洁的方法
C mouse event and keyboard event of C (XXVIII)
《2022年中国银行业RPA供应商实力矩阵分析》研究报告正式启动
No qualifying bean of type ‘......‘ available
Esp32 (based on Arduino) connects the mqtt server of emqx to upload information and command control
math_极限&微分&导数&微商/对数函数的导函数推导(导数定义极限法)/指数函数求导公式推导(反函数求导法则/对数求导法)
20、 EEPROM memory (AT24C02) (similar to AD)
阿里测试师用UI自动化测试实现元素定位
【FPGA教程案例11】基于vivado核的除法器设计与实现
Record an excel xxE vulnerability
Basic concepts of LTE user experience
How to modify field constraints (type, default, null, etc.) in a table