4/1 最小生成树+最短路+floyed+图中深搜
生成 最小 短路 图中
2023-09-11 14:15:53 时间
P1194 买礼物
输入时需要特殊处理,若不加(x!=0),只能过一组样例,wa了三次,很烦~
数据中没有优惠是0,因此不同产品间若是0则不需要建边,但实际情况中是存在的,而且题目也没说,不纠结了。
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int a,b,cnt,f[N],ans,g;
struct node
{
int u,v,dis;
}e[N];
bool cmp(node e1,node e2)
{
return e1.dis<e2.dis;
}
int r_find(int r)
{
if(r==f[r]) return r;
f[r]=r_find(f[r]);
return f[r];
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin>>a>>b;
for(int i=1;i<=b;i++) f[i]=i;
for(int i=1;i<=b;i++)
for(int j=1;j<=b;j++)
{
int x;cin>>x;
if(j<=i||x==0) continue;
e[++cnt].u=i,e[cnt].v=j,e[cnt].dis=x;
}
for(int i=1;i<=b;i++)
{
e[++cnt].u=0,e[cnt].v=i,e[cnt].dis=a;
}
sort(e+1,e+cnt+1,cmp);
for(int i=1;i<=cnt;i++)
{
int fx=r_find(e[i].u),fy=r_find(e[i].v);
if(fx==fy) continue;
g++;
f[fx]=fy;
ans+=e[i].dis;
if(g==b-1) break;
}
cout<<ans+a<<endl;
return 0;
}
P1346 电车
习惯了链式前向行,尽管这题不需要。
感觉spfa算法处理一般的最短路更方便点
#include <bits/stdc++.h>
using namespace std;
const int N=3e3+5;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,a,b,dist[N],head[N],cnt;
bool vis[N];
struct node
{
int to,nxt,dis;
}e[N*N];
void add(int from,int to,int dis)
{
e[++cnt].to=to;
e[cnt].dis=dis;
e[cnt].nxt=head[from];
head[from]=cnt;
}
void dijstra()
{
for(int i=1;i<=n;i++) dist[i]=inf;
dist[a]=0;
queue<int>q;q.push(a);vis[a]=1;
while(!q.empty())
{
int u=q.front();q.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(dist[v]>dist[u]+e[i].dis)
{
dist[v]=dist[u]+e[i].dis;
if(!vis[v])
{
vis[v]=1;q.push(v);
}
}
}
}
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>a>>b;
for(int i=1;i<=n;i++)
{
int k;cin>>k;
for(int j=1;j<=k;j++)
{
int x;cin>>x;
if(j==1)
add(i,x,0);
else
add(i,x,1);
}
}
dijstra();
if(dist[b]==inf)
cout<<"-1"<<endl;
else
cout<<dist[b]<<endl;
return 0;
}
P1476 休息中的小呆
光题意就挺难懂得。
1.共n个剧情点,要想到共有n+1个剧情。
2.采用floyed算最常路。因为要完成所有的剧情任务,如果需要时间最长的完成了,则其他的肯定也完成了!比较抽象。
3.由于是全源最短路,设置间断点看经过了哪些点
#include <bits/stdc++.h>
using namespace std;
const int N=1e2+5;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int mp[N][N],dist[N],n,m;
signed main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,z;cin>>x>>y>>z;
mp[x][y]=z;
}
//n个剧情结束点,说明有n+1个剧情
for(int k=1;k<=n+1;k++)
for(int i=1;i<=n+1;i++)
for(int j=1;j<=n+1;j++)
{
if(i!=j&&j!=k&&mp[i][k]&&mp[k][j])
if(mp[i][j]<mp[i][k]+mp[k][j])
{
mp[i][j]=mp[i][k]+mp[k][j];
}
}
cout<<mp[1][n+1]<<endl;
for(int i=1;i<=n+1;i++)
if(mp[1][i]+mp[i][n+1]==mp[1][n+1])
cout<<i<<" ";
cout<<endl;
return 0;
}
P1661 扩散
floyed算法:根据两点间得曼哈顿距离建图
比较i到k
和k到j
中取较大得那个,最后结果/2.
#include <bits/stdc++.h>
using namespace std;
const int N=1e2+5;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int mp[N][N],n,a[N],b[N],mx;
signed main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j)
mp[i][j]=abs(a[i]-a[j])+abs(b[i]-b[j]);
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i!=j&&j!=k&&mp[i][k]&&mp[k][j])
{
mp[i][j]=min(mp[i][j],max(mp[i][k],mp[k][j]));
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
mx=max(mx,mp[i][j]);
cout<<(mx+1)/2<<endl;
return 0;
}
P1692 部落卫队
对于深搜得代码还是不够熟练。dfs中若是思路不够清晰,不要轻易写for循环,增加复杂度。
此代码数据范围大的过不了~
#include <bits/stdc++.h>
using namespace std;
const int N=1e2+5;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int mp[N][N],n,m,ans,mx,a[N];
bool vis[N];
bool check(int x) //选的这个人于队里是否有矛盾
{
for(int i=1;i<=n;i++)
{
if(vis[i]&&mp[x][i]) return 0; //如果这个人之前选过并且和待选的人有仇,就不能选
}
return 1;
}
void dfs(int u,int num) //搜索到第几个人,队里人数
{
if(u==n+1) //搜索完所有人,结束
{
if(mx<num)
{
mx=num;
for(int i=1;i<=n;i++) //记录选人的状态
a[i]=vis[i];
}
return;
}
if(!vis[u]&&check(u)) //对于一个人选和不选,这里满足条件进入if语句可以选
{
vis[u]=1;
dfs(u+1,num+1);
vis[u]=0;
}
dfs(u+1,num); //不选
}
signed main()
{
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;cin>>u>>v;
mp[u][v]=1;mp[v][u]=1;
}
dfs(1,0); //从第一个人开始,队里没人
cout<<mx<<endl;
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
相关文章
- 最小生成树(Kruskal+Prim)--模板
- TestNG+ExtentReports生成超漂亮的测试报告(转)
- Java实现 蓝桥杯 算法提高最小方差生成树
- 设计稿生成代码与 Serverless 的前世今生与未来!
- Java运行时动态生成类几种方式
- PowerDesigner 12 根据名称生成注释(完整示例)
- Open3D (C++) 最小生成树用于法向量定向
- CloudCompare——生成常见几何点云
- 【BZOJ 1016】[JSOI2008]最小生成树计数(搜索+克鲁斯卡尔)
- Eclipse自动生成get和set方法
- 全国 省市 自治区的数据库sql生成
- 十大基础有用算法之迪杰斯特拉算法、最小生成树和搜索算法
- POJ 1679 The Unique MST 推断最小生成树是否唯一
- 图的最小生成树-Kruskal算法
- Leetcode 1374. 生成每种字符都是奇数个的字符串
- 图论---最小生成树
- POJ 1861 & ZOJ 1542 Network(最小生成树之Krusal)
- LabVIEW报告生成工具包VI断开
- HDU 1863 畅通project (最小生成树是否存在)
- 经典树与图论(最小生成树、哈夫曼树、最短路径问题---Dijkstra算法)
- Python小白的数学建模课-18.最小生成树问题
- Android Studio 扫描识别二维码(包含闪光灯和本地二维码)、生成二维码、生成带logo的二维码
- LSGANs : Least Squares GAN(最小二乘GAN)--解决标准GAN生成的图片质量不高以及训练过程不稳定问题