题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3810
题意：Magina 去打怪，目的是在最短的时间内得到ｍ units money。已知有Ｎ个怪分布在Ｎ个地点，打每一怪可以获得ｇｉ ｍｏｎｅｙ，但同时也需要花ｔｉ 时间。Ｍａｇｉｎａ 可以任意的选择一个怪开始打，已知他又一个技能，就是瞬间移动啦，从一个地方到另一个地方，不需要花费时间，但前提是这俩个地方是相连的，打完一个怪之后，该怪物就会消失，同时那个相连的路也会跟着消失。
分析：大致题意就是这样了，一开始就是直接搜啦，很笨的方法，是因为没注意到一个问题，“ For every spots, Magina may use Ti time to kill the monsters and gain Gi units money, or he choose blink to other spots”，ｏｒｚ，达到每一个地点时，他可以选择不打，然后通过该地点转移到另一个地点，也就是说，对于每一个连通分量，他可以打任何一个怪。所以，剪枝就这里了，先用简单的ＤＦＳ（）搜出当前的整个连通分量，记录下中途可以遇到的所有怪。那么对于当前的连通分量，就可能组合出一个花费最小时间而获得至少ｍ ｍｏｎｅｙ的打怪顺序了。当然，我们并不需要记录打怪的顺序，所以问题又简化了。
接下来就是组合出一个结果了：
搜出一个连通分量之后，保存所有遇到的怪到ｑ［］结构体中，再对其排序（针对打怪获得的ｍｏｎｅｙ从小到大）（算是一个剪枝吧），之后就在该结构体数组里面搜索，搜出符合条件的结果；
#include<iostream>
#include<string.h>
#include<algorithm>
#define maxn 2000000001
using namespace std;
bool g[55][55],vis[55];
struct spots
{
int t,u;
}p[55],q[55];
int n,m,qt,ans,hp;
int nextsum[55];
void DFS(int a)
{
vis[a]=true;
q[qt++]=p[a];
hp+=p[a].u;
if(hp>m)
hp=m;
for(int i=1;i<=n;i++)
if(g[a][i] && !vis[i])
DFS(i);
}
void search(int x,int t,int u)
{
if(x==qt)//结构体数组没有元素了
return;
if(t>ans)//大于目前已有的解，则也不必要搜下去了
return;
if(u+nextsum[x]<m)//因为已经排序了，后面已经没有符合条件的了
return ;
if(u+q[x].u>=m)
{
ans=min(ans,t+q[x].t);
search(x+1,t,u);
}
else {
search(x+1,t,u);
search(x+1,t+q[x].t,u+q[x].u);
}
}
bool cmp(spots a,spots b)
{
return a.u>b.u;
}
int main()
{
int T,cas=0,k,a;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&m);
memset(g,0,sizeof(g));
for(int i=1;i<=n;i++)
{
scanf("%d %d %d",&p[i].t,&p[i].u,&k);
while(k--)
{
scanf("%d",&a);
g[i][a]=1;
}
}
memset(vis,0,sizeof(vis));
ans=maxn;
for(int i=1;i<=n;i++)
{
hp=0;
qt=0;
if(!vis[i])
DFS(i);
if(hp<m) continue;
sort(q,q+qt,cmp);
nextsum[qt-1]=q[qt-1].u;
for(int j=qt-2;j>=0;j--)
{
nextsum[j]=nextsum[j+1]+q[j].u;
if(nextsum[j]>m)
nextsum[j]=m;
}
search(0,0,0);
}
printf("Case %d: ",++cas);
if(ans!=maxn)
printf("%d\n",ans);
else printf("Poor Magina, you can't save the world all the time!\n");
}
return 0;
}