旅行 题解

1.题目

题目传送门

2.解题

分析

本题属图论，可以选定一个城市作为起点，再深度优先搜索(dfs)去寻找能到达的城市，同时为避免重复，到过的城市要做标记，防止走了一圈又绕回来。 可得初代dfs代码：

const int TOP=3000;
int n/*城市数*/,m/*道路数*/;
int a[TOP],b[TOP];//道路起点及道路终点
bool biaoji[TOP];//标记当前城市是否来过
int ans;
void dfs(int fir/*起始城市*/,int now/*当前城市*/)
{
	if(biaoji[now])//到达过的城市去重
		return ;
	int f;
	ans++;//到达城市+1
	biaoji[now]=true;//记录：此城市已到达
//	cout<<'('<<fir<<','<<now<<')'<<endl;
	for(f=1;f<=m;f++)//遍历每一条道路，寻找下一个目的地
	{
		if(a[f]==now)
			dfs(fir,b[f]);
	}
	return ;
}

将其他部分补充完整，整体代码就完成了：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int TOP=3000;
int n/*城市数*/,m/*道路数*/;
int a[TOP],b[TOP];
bool biaoji[TOP];//标记当前城市是否来过
int ans;
void dfs(int fir/*起始城市*/,int now/*当前城市*/)
{
	if(biaoji[now])
		return ;
	int f;
	ans++;
	biaoji[now]=true;
//	cout<<'('<<fir<<','<<now<<')'<<endl;
	for(f=1;f<=m;f++)
	{
		if(a[f]==now)
			dfs(fir,b[f]);
	}
	return ;
}
signed main()
{
	freopen("lx.in","r",stdin);
	freopen("lx.out","w",stdout);
	int f,k;
	cin>>n>>m;
	for(f=1;f<=m;f++)
		cin>>a[f]>>b[f];
	for(f=1;f<=n;f++)
	{
		dfs(f,f);
		memset(biaoji,false,n+1);
	}
	cout<<ans;
	return 0;
}

提交，然后就

改进代码

因为问题出在超时上，就着重看那些地方能削减时间复杂度。这时，dfs中循环遍历路径就显得非常冗余，通过优化存储方式，比如利用类似"桶"的存储模式，就可以一步到位，不用麻烦地寻找了。 于是，就得到了改进版的dfs代码

const int TOP=3000;
int n/*城市数*/,m/*道路数*/;
vector<vector<int> > t(TOP);
//t[f]存储从f城市出发，能到达哪些城市
bool biaoji[TOP];//标记当前城市是否来过
int ans;
void dfs(int now/*当前城市*/)
{
	if(biaoji[now]) return ;
	ans++;//到达城市+1
	biaoji[now]=true;//来过了，做个标记
	int tmp=t[now].size();
    //因为求一次size要o(n)的时间复杂度，就保存一下
	for(int f=0;f<tmp;f++)
      dfs(t[now][f]);//遍历下一个城市
	return ;
}

补充其它部分，得到最终版：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int TOP=3000;
int n/*城市数*/,m/*道路数*/;
vector<vector<int> > t(TOP);
bool biaoji[TOP];//标记当前城市是否来过
int ans;
void dfs(int now/*当前城市*/)
{
	if(biaoji[now]) return ;
	ans++;
	biaoji[now]=true;
	int tmp=t[now].size();
	for(int f=0;f<tmp;f++) dfs(t[now][f]);
	return ;
}
signed main()
{
//	freopen("lx.in","r",stdin);
//	freopen("lx.out","w",stdout);
	int f,k;
	cin>>n>>m;
	for(f=1;f<=m;f++)
	{
		int a,b;
		cin>>a>>b;
		t[a].push_back(b);
	}
	for(f=1;f<=n;f++)
	{
		dfs(f);
		memset(biaoji,false,n+1);
	}
	cout<<ans;
	return 0;
}

果断AC

诚信做人，请勿抄袭