阅读程序

注意：切勿用电脑直接运行代码得出答案，请用大脑+笔+纸运行代码答题，否则是在浪费你的时间。

第9节：树和图

第5题【NOIP】2011

#include<iostream>
using namespace std;
const int V=100;
int n,m,ans,e[V][V];
bool visited[V];
void dfs(int x,int len)
{
    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;
    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;
}

●判断题

(1)输入的数据应满足a,b<100。

{{ select(5-1) }}

• 正确
• 错误

(2)该程序实现的是多源最短路。

{{ select(5-2) }}

• 正确
• 错误

(3)在没有重边与自环的情况下，m最大为$n^2$

{{ select(5-3) }}

• 正确
• 错误

(4)对于一个n个点的边权均为w的完全图，输出为(n—1)*w。

{{ select(5-4) }}

• 正确
• 错误

●选择题

(5)求该程序消耗空间约为()

{{ select(5-5) }}

• 100MB
• 1GB
• 40KB
• 100KB

(6)

输人：

46
12 10
23 20
34 30
41 40
13 50
24 60

输出()。

{{ select(5-6) }}

• 150
• 60
• 210
• 10