• 首页
  • 教育理念
  • 文章专题
  • 编程教程
    • – Scratch编程教程
    • – AppInventor编程
    • – Python编程教程
    • – NOIP信息学奥赛
    • – C/C++编程教程
    • – JS编程教程
  • 少儿编程学院
    • – 在线课程
    • – 学院名师
    • – 动态资讯
  • 少儿编程社区
    • – 在线编程
    • – 编程作品
    • – 专题创作
  • 更多
    • – APP客户端
    • – 关于我们
    • – 寻求合作
    • – 少儿编程联盟
投稿 登录 注册
  • 首页
  • 文章专题
  • 教育理念
  • 编程教程
  • 少儿编程学院
  • 微信公众号
  • APP客户端
少儿编程学院
少儿编程教育-微信公众号
首页 › 编程教程 › NOIP信息学奥赛 › 正文
NOIP信息学奥赛信息竞赛编程竞赛

NOIP复赛复习(五)程序对拍与图论模板

主编主编 NOIP信息学奥赛 2017-10-04 2,254 0

程序对拍

所谓“对拍”,顾名思义,就是让两者相互比对。所谓“两者”,一是你要测试的程序,二是一个答案在该程序在一定范围(时间/空间)内结果必定正确的程序(一般是用暴力求解的程序)。对拍一般需要造数据程序(data.exe),保证正确性的暴力对拍程序(test.exe)与测试程序(以moo.exe为例)。下面是对拍的代码,写在txt中再转成.bat即可。
:loop
data.exe
test.exe
moo.exe
fc moo.out test.out
if %errorlevel% ==0goto loop
pause


图论算法

1、图的遍历-BFS

#include<iostream>
#include <queue>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 1, 0 },
{ 0, 1, 1, 1, 0 },
{ 1, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0 }
};
int visited[N + 1] = {0, };
void BFS(int start)
{
queue<int> Q;
Q.push(start);
visited[start] = 1;
while (!Q.empty())
{
int front = Q.front();
cout << front << "";
Q.pop();
for (int i = 1; i <= N; i++)
{
if (!visited[i] &&maze[front - 1][i - 1] == 1)
{
visited[i] = 1;
Q.push(i);
}
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
BFS(i);
}
return 0;
}

2、图的遍历-DFS

#include<iostream>
#include <stack>
#define N 5
using namespace std;
int maze[N][N] = {
{ 0, 1, 1, 0, 0 },
{ 0, 0, 1, 0, 1 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 0, 0, 1 },
{ 0, 0, 1, 0, 0 }
};
int visited[N + 1] = {0, };
void DFS(int start)
{
stack<int> s;
s.push(start);
visited[start] = 1;
bool is_push = false;
while (!s.empty())
{
is_push = false;
int v = s.top();
for (int i = 1; i <= N; i++)
{
if (maze[v - 1][i - 1] == 1&& !visited[i])
{
visited[i] = 1;
s.push(i);
is_push = true;
break;
}
}
if (!is_push)
{
cout << v << " ";
s.pop();
}
}
}
int main()
{
for (int i = 1; i <= N; i++)
{
if (visited[i] == 1)
continue;
DFS(i);
}
return 0;
}

3、最小生成树-Kruskal

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN = 30;
int pa[MAXN];
int rank[MAXN];
int n,sum;
struct node{
int x,y;
int w;
}edge[MAXN*MAXN];
bool cmp(node p,node q){
return p.w<q.w;
}
void make_set(int x)
{
pa[x] = x;
rank[x] = 0;
}
int find_set(int x)
{
if(x != pa[x])
pa[x] = find_set(pa[x]);
return pa[x];
}
void union_set(int x, int y,int w)
{
x = find_set(x);
y = find_set(y);
if(x == y)return ;
if(rank[x] > rank[y])
{
pa[y] = x;
}
else
{
pa[x] = y;
if(rank[x] == rank[y])
rank[y]++;
}
sum+=w;
}
int main()
{
//  freopen("input.txt","r",stdin);
while(cin>>n){
if(!n) break;
char ch;
int m,k=0;
for (int i = 0; i < n - 1; i++)
{
cin >> ch >> m;
for (int j = 0; j < m; j++)
{
cin >> ch >> edge[k].w;
edge[k].x = i;
edge[k].y = ch - 'A';
k++;
}
}
sort(edge,edge+k,cmp);
for(int i=0;i<MAXN;i++)
make_set(i);
sum=0;
for(int i=0;i<k;i++)
union_set(edge[i].x,edge[i].y,edge[i].w);
cout<<sum<<endl;
}
}

4、最小生成树-Prim

#include<cstdio>
using namespace std;
const int maxn=30;
const int INF=1000000;
int graph[maxn][maxn];
int lowcost[maxn],closet[maxn];
int visited[maxn];
int n;
void createGraph(){
memset(graph,0,sizeof(graph));
memset(lowcost,0,sizeof(lowcost));
memset(closet,0,sizeof(closet));
memset(visited,0,sizeof(visited));
int a;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
scanf("%d",&a);
if(a==0)
graph[i][j]=graph[j][i]=INF;
else
graph[i][j]=graph[j][i]=a;
}
}
void prim(){
int sum=0;
visited[0]=1;
for(int i=0;i<n;i++){
lowcost[i]=graph[i][0];
closet[i]=0;
}
for(int i=1;i<n;i++){
int minn=lowcost[0],k=0;
for(int j=0;j<n;j++){
if(!visited[j] && lowcost[j]<minn){
minn=lowcost[j];
k=j;
}
}
sum+=minn;
visited[k]=1;
for(int t=0;t<n;t++){
if(!visited[t] && lowcost[t]>graph[t][k]){
lowcost[t]=graph[t][k];
closet[t]=k;
}
}
}
printf("%d\n",sum);
}
int main()
{
// freopen("input.txt","r",stdin);
while(~scanf("%d",&n)){
if(!n) break;
createGraph();
prim();
}
}

5、最短路径-SPFA

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
const int maxn=100005;
struct dqs
{
int f,t,c;
}hh[maxn];
int tot=0,first[maxn],next[maxn],d[maxn];
bool used[maxn];
void build(int f,intt,int c)
{
hh[++tot]=(dqs){f,t,c};
next[tot]=first[f];
first[f]=tot;
}
queue<int>q;
int n,m,s,e;
void spfa(int s)
{
d[s]=0;
q.push(s);
used[s]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
used[x]=0;
for(int i=first[x];i;i=next[i])
{
int u=hh[i].t;
if(d[u]>d[x]+hh[i].c)
{
d[u]=d[x]+hh[i].c;
if(!used[u])
{
q.push(u);
used[u]=1;
}
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&e);
for(int i=1;i<=n;i++)
d[i]=1e9;
for(int i=1;i<=m;i++)
{
int f,t,c;
scanf("%d%d%d",&f,&t,&c);
build(f,t,c);
build(t,f,c);
}
spfa(s);
printf("%d\n",d[e]);
return 0;
}

6、最短路径-Dijkstra

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=100005;
struct dqs
{
int f,t,c;
}hh[maxn];
int tot=0,first[maxn],next[maxn],d[maxn];
bool used[maxn];
void build(int f,intt,int c)
{
hh[++tot]=(dqs){f,t,c};
next[tot]=first[f];
first[f]=tot;
}
int n,m,s,e;
void Dijkstra()
{
for(int i=1;i<=n;i++)
d[i]=1e9;
d[s]=0;
while(true)
{
int x=-1;
for(int i=1;i<=n;i++)
{
if(!used[i])
if(x==-1||d[i]<d[x])
x=i;
if(x==-1) break;
used[x]=1;
for(int i=first[x];i;i=next[i])
{
int u=hh[i].t;
if(d[u]>d[x]+hh[i].c)
d[u]=d[x]+hh[i].c;
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&e);
......
}

7、最短路径-Floyd

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=1005;
int d[maxn][maxn];
int n,m,s,e;
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&i!=k&&k!=j)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&e);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=1e9;
for(int i=1;i<=m;i++)
{
int f,t,c;
scanf("%d%d%d",&f,&t,&c);
d[f][t]=c;
d[t][f]=c;
}
floyd();
printf("%d\n",d[s][e]);
return 0;
}

8、最近公共祖先(LCA)-倍增

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=250010;
struct dqs
{
int f,t,c;
}hh[maxn<<1];
int tot=0,fa[maxn][31],next[maxn],first[maxn],f[maxn],d[maxn];
void build(int ff,inttt,int cc)
{
hh[++tot]=(dqs){ff,tt,cc};
next[tot]=first[ff];
first[ff]=tot;
}
int deep[maxn];
void dfs(int x,int sd)
{
deep[x]=sd;
int u;
for(int i=first[x];i;i=next[i])
{
u=hh[i].t;
if(!deep[u]&&u)
{
f[u]=x;
d[u]=d[x]+hh[i].c;
dfs(u,sd+1);
}
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y])
swap(x,y);
int deepcha=deep[x]-deep[y];
for(int i=0;i<=30;i++)
{
if(1<<i&deepcha)
x=fa[x][i];
}
for(int i=30;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
}
if(x!=y)
return f[x];
return x;
}
int main()
{
int n;
scanf("%d",&n);
int u,v,c;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&c);
build(u,v,c);
build(v,u,c);
}
dfs(0,0);
for(int i=0;i<n;i++)
fa[i][0]=f[i];
for(int j=1;j<=20;j++)
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
int xx=lca(u,v);
printf("%d\n",d[u]+d[v]-2*d[xx]);
}
return 0;
}

*
喜欢 (0)
打赏
  • 打赏支付宝扫一扫
  • 打赏微信扫一扫
微博 微信 QQ

微信扫一扫,分享到朋友圈

微信公众号
编程少年Scratch实物积木
少儿编程教育-微信公众号
上一篇

NOIP复赛复习(四)读写外挂与高精度模板

下一篇

NOIP复赛复习(六)算法分析与排序模板

猜你喜欢

  • 第二届全国中学生网络安全竞赛即将在西安电子科大举办!

    第二届全国中学生网络安全竞赛即将在西安电子科大举办!

  • 严查违规竞赛,29项全国中小学生竞赛活动名单公布!

    严查违规竞赛,29项全国中小学生竞赛活动名单公布!

  • 教育部:2019年度中小学生全国性竞赛活动名单公示

    教育部:2019年度中小学生全国性竞赛活动名单公示

  • 第二十届全国中小学电脑制作活动通知

    第二十届全国中小学电脑制作活动通知

  • 2018年全国青少年创意编程大赛,终评活动即将开启!

    2018年全国青少年创意编程大赛,终评活动即将开启!

  • STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

    STEAM教育专题 | 源自硅谷的机器人教育机构萝卜太辣

主编
主编官方

我真的不是自黑!

中国STEAM教育2018年度风云榜

微信公众号

推荐专题

  • 有趣的少儿编程游戏推荐

    查看专题
  • 国外优秀的少儿编程教育

    查看专题
  • S科学-T技术-E工程-M数学

    查看专题

猜你喜欢

  • 必看丨无奖项考生报考自主招生,这些疑问你也有吗 ?
    2018-08-08

    必看丨无奖项考生报考自主招生,这些疑问你也有吗 ?

  • 少儿编程教育对于基础教育有什么核心价值?

    少儿编程教育对于基础教育有什么核心价值?

    2018-04-06
  • 大数据时代对教育理念和教育方式带来的影响和冲击

    大数据时代对教育理念和教育方式带来的影响和冲击

    2018-05-23
  • 免费领取Google谷歌中小学计算机思维课程中文课件!

    免费领取Google谷歌中小学计算机思维课程中文课件!

    2018-01-09
  • 浙大自主招生:自主招生最难的不是初审,笔试难倒无数英雄豪杰!

    浙大自主招生:自主招生最难的不是初审,笔试难倒无数英雄豪杰!

    2018-08-20

热门文章

    暂无文章

热门标签

鲨鱼公园高考改革高考加分青橙创客青少儿防疫阿部和广错误观念逻辑思维费米科学贝尔科教谷歌教育计算机科学计算机思维解决方案西瓜创客

微信公众号

热门文章 热门标签 年度归档 少儿编程教育联盟

Copyright © 2021 少儿编程教育网 粤ICP备17057575号 · Designed by shaoerbc.org

大家都在搜

  • Scratch教程
  • scratch2下载
  • Scratch编程
  • 编程思维
  • 信息学奥赛
  • STEM教育
  • 编程一小时
  • 自主招生
  • 少儿编程竞赛

关注我们的公众号

微信公众号