2022年NOIP提高组初赛历年试题及答案阅读题篇.pdf

: .
#include <iostream>vip 会员免费
using namespace std;
const int V=100;
int n,m,ans,e[V][V];
bool visited[V];
void dfs(int x,intlen)
{
int i;
visited[x]= true;
if(len>ans)
ans=len;
for(i=1;i<=n;i++)
if( (!visited[i]) &&(e[x][i]!=-1) )
dfs(i,len+e[x][i]);
visited[x]=false;
}
int main()
{
int i,j,a,b,c;
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
e[i][j]=-1;vip 会员免费
for(i=1;i<=m;i++)
{
cin>>a>>b>>c;
e[a][b]=c;
e[b][a]=c;
}
for(i=1;i<=n;i++)
visited[i]=false;
ans=0;
for(i=1;i<=n;i++)
dfs(i,0);
cout<<ans<<endl;
return 0;
}
输入：
4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60vip 会员免费
一看就知这是深搜算法（ DFS ），输入是个四个顶点的无向图（邻接矩阵如下）：
如 len>ans ，则 ans=len ，可以说明这是个在图中用 DFS 找最长的路径的程序。 DFS 以任
意点作为起点，找一条路径，本次走过的点不走，找到没路走为止。由于就 4 个点，最多
就走 3 条边，看看最长的那 3 条，结果如下图：vip 会员免费
输出： 150
NOIP2011-4 ．
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int SIZE=10000;
const int LENGTH=10;
int n,m,a[SIZE][LENGTH];
int h(int u,int v)
{
int ans,i;
ans=0;
for(i=1;i<=n;i++)vip 会员免费
if( a[u][i]!=a[v][i])
ans++;
return ans;
}
int main()
{
int sum,i,j;
cin>>n;
memset(a,0,sizeof(a));
m=1;
while(1)
{
i=1;
while( (i<=n) &&(a[m][i]==1) )
i++;
if(i>n)
break;
m++;
a[m][i]=1;
for(j=i+1;j<=n;j++)
a[m][j]=a[m-1][j];
} : .
vip 会员免费
NOIP