枚举（数据较小）+BFS ，再有重要的一点是剪枝！
类似的题目及解题报告：
枚举常常被用作辅助算法，与其它算法一起解题。
pku 1062：
昂贵的聘礼
图论的题目，容易想到增加一个起点S, 使花费转移到边上。
即，若某物品Ai的价格为Pi, 添一条权值为Pi的边S-->Ai
若物品Aj可以用Ai加优惠价Qi换得,加权值为Qi的边Ai-->Aj，形成母图。问题就成了一个最短路，不过有附加限制。
针对限制——在交易的所有人中地位最高的和地位最低的等级差在m以内，对可行的子图枚举。
除了S,每个点都有一个rank,枚举rank最大的点(从1到n),不妨设其rank值为R0,除去rank大于R0的,以及rank小于R0-m的.在剩余的图中求S到A1
的最短路，容易解决。
数据结构：邻接矩阵。
复杂度 O(n^3)
框架：1.枚举{2.构图,3.最短路(局部最优)}4.最优解（全局）
pku 1042 Gone Fishing 是大家比较熟悉的一道题目了，不再详述题意。
精彩之处在于枚举了最远的湖之后，人就可以瞬间移动，从而不受不能返回的限制，可以用贪心解决了。
复杂度 O(n^2)
框架：1.枚举 {2.局部最优（贪心）}3.全局最优
再如，pku 3311 Hie with the Pie，由于N 比较小，(N-1)!<=9!，还是可以接受的，应该可以枚举,(当然，还有别的解法)。预处理是先运行
一遍floyed.
附AC代码：
///
Problem Id:1062 User Id:sanpin ///
Memory:276K Time:77MS ///
Language:G++ Result:Accepted ///
///
Source
#include <iostream>
#include <algorithm>
#define N 105
#define MM 1000000000
using namespace std;
int cost[N][N],m,n;
int newCost[N][N];
int rank[N];
void input()
{
int i,j,k;
int f,v;
cin>>m>>n;
++n;
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
cost[i][j]=MM;
}
for (k=1;k<n;k++)
{
cin>>cost[0][k]>>rank[k];
cin>>f;
while (f--)
{
cin>>v;
cin>>cost[v][k];
}
}
}
int dijkstra(int from, int to, int map[][N])
{
int* dis=new int[n];
int* s=new int[n];
int mindis;
int i,j,u;
for(i=0;i<n;i++)
{
dis[i]=map[from][i];
s[i]=0;
}
s[from]=1;
while (!s[to])
{
mindis=MM;
u=-1;
for(j=0; j<n; j++)
{
if(s[j]==0 && dis[j]<mindis)
{
u=j;
mindis=dis[j];
}
}
if (mindis>=MM)
goto lable;
s[u]=1;
for(j=0;j<n;j++)
{
if(s[j]==0)
{
if(map[u][j]<MM && dis[u]+map[u][j]<dis[j])
{
dis[j]=dis[u]+map[u][j];
}
}
}
}
mindis=dis[to];
lable:delete[] dis;
delete[] s;
return mindis;
}
int solve()
{
int highRank;
int i,j;
int dist=MM;
int hst=-1,lst=n;
for (i=1;i<n;i++)
{
if (rank[i]>hst)
hst=rank[i];
if (rank[i]<lst)
lst=rank[i];
}
for (highRank=min(lst+m,hst);highRank<=hst;highRank++)//枚举最高的rank
{
//生成新图
rank[0]=highRank;//保证0被包括在内
for (i=0;i<=n;i++)
{
for (j=0;j<=n;j++)
{
if (rank[i]>highRank||rank[j]>highRank||rank[i]<highRank-m||rank[j]<highRank-m)
newCost[i][j]=MM;
else
newCost[i][j]=cost[i][j];
}
}
int t;
if ((t=dijkstra(0,1,newCost))<dist)
dist=t;
}
return dist;
}
int main()
{
input();
cout<<solve()<<endl;
return 0;
}
/
Problem Id:1042 User Id:sanpin ///
Memory:192K Time:212MS ///
Language:G++ Result:Accepted ///
/
Source
#include <iostream>
#include <algorithm>
using namespace std;
const int Mn=26;
int n,h;
int fishTotal[Mn],fishDec[Mn],wayTime[Mn];
int timeStay[Mn],finalTime[Mn];
int tellMax(int *a,int e)
{
int i,r=0,s=0;
for(i=0;i<e;i++)
{
if (a[i]>s)
{
r=i;
s=a[i];
}
}
return r;
}
int solve()
{
int fishAvail[Mn];
int k,i;
int tt=0,ms=-1,ts;
int timeLeft=h;
for (k=1;k<=n;k++)
{
tt+=wayTime[k-1]*5;
if ( tt > h )
break;
timeLeft=h-tt;
memcpy(fishAvail,fishTotal,sizeof(fishTotal));
memset(timeStay,0,sizeof(timeStay));
i=0,ts=0;
while (timeLeft>0)
{
i=tellMax(fishAvail,k);
ts+=fishAvail[i];// 鱼量
timeStay[i]+=5;//时间
timeLeft-=5;
fishAvail[i]=fishAvail[i]-fishDec[i];
if (fishAvail[i]<0)
fishAvail[i]=0;
}
if (ts>ms)
{
ms=ts;
memcpy(finalTime,timeStay,sizeof(timeStay));
}
}
return ms;
}
int main()
{
int i;
while (cin>>n)
{
if (n==0)break;
memset(finalTime,0,sizeof(finalTime));
cin >> h;
h *= 60;
for (i=0;i<n;i++) cin>>fishTotal[i];
for (i=0; i<n; i++) cin >> fishDec[i];
wayTime[0]=0;
for (i=1;i<n;i++) cin >> wayTime[i];
int t= solve();
for (i=0;i<n-1;i++)
{
cout<<finalTime[i]<<", ";
}
cout<<finalTime[i]<<endl;
cout<<"Number of fish expected: "<<t<<' '<<endl<<endl;
}
return 0;
}
/
Problem Id:3311 User Id:sanpin //
Memory:296K Time:234MS //
Language:G++ Result:Accepted //
/
Source
#include <iostream>
#include <algorithm>
#define N 11
#define MM 10000000
using namespace std;
int gh[N][N];
int cost[N][N];
bool visited[N];
int n;
/*
floyd-warshall algrithm
n is the number of nodes
sp[i][j] is the shortest path between i and j
sp is initialized the edge between i and j, Max if no edge
attention sp[i][i]===0;
*/
const int Max=1000000000;
void Floyd(int n, int sp[][N])
{
int i, j, k;
for (k=0; k<n; k++)
{
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
{
if (sp[i][j]>sp[i][k]+sp[k][j])
{
sp[i][j]=sp[i][k]+sp[k][j];
}
}
}
}
}
int path[N];
int f()
{
int re=MM,s,i;
for (i=0;i<n;i++)
path[i]=i;
path[n]=0;
do
{
s=0;
for (i=0;i<n;i++)
{
s+=gh[path[i]][path[i+1]];
}
re=min(re,s);
}
while (next_permutation(path+1,path+n));//except first and last '0'
return re;
}
int main()
{
int i,j;
while (cin>>n)
{
if (n==0)break;
++n;
memset(visited,false,sizeof(visited));
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
cin>>gh[i][j];
}
Floyd(n,gh);
visited[0]=true;
cout<<f()<<endl;
}
return 0;
}
“在很多时候无法立刻得出问题的可行解或者最优解，但是可以用一种比较“笨“的方法，列举所有情况然后逐一判断来得到结果，这就是枚
举算法的核心思想。”－－－－lrj
“在问题毫无头绪的情况下，枚举为我们打开一个缺口，让其它算法可以成功”————lrj