点炸弹(bfs+剪枝，或链式向前星+剪枝+bfs)

本文主要是介绍点炸弹(bfs+剪枝，或链式向前星+剪枝+bfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1779: 三队-杭州-点炸弹

Time Limit: 1 Sec   Memory Limit: 128 MB
Submit: 57   Solved: 12
[ Submit][ Status][ Web Board]

Description

Input

Output

Sample Input

150 0 1 51 1 1 60 1 1 73 0 2 105 0 1 4

Sample Output

Case #1: 18

HINT

Source

把能爆炸的炸弹连起来，可以得到一张有向图。可以对所有的点跑一遍bfs，得出最优解。但这样会超时，需要加入剪枝。对于要bfs的一个点i，遍历与这个点相连的点，如果与他相邻的点j和他能互爆，j点的值已经得到，那么i点的值就是j点的值。通过这种剪枝即可。对于存图，用链式向前星会快一些。链式向前星是一个种存边的方法，能从图中任一点出发，遍历整张图。

原题链接：点击打开链接

#include<iostream>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;
vector<int>V[1005];
queue<int>Q;
int x[1005],y[1005],r[1005],c[1005];
int vis[1005];
int head[1005];
int con[1005][1005];
long long val[1005];
int cnt;
struct Edge
{int next;int to;int w;
}edge[10000005];
void add(int u,int v,int w)
{edge[cnt].w = w;edge[cnt].to = v;edge[cnt].next = head[u];head[u] = cnt++;
}
bool canboom(int a,int b)//a能引爆b 
{long long dx=x[a]-x[b];long long dy=y[a]-y[b];long long dis=dx*dx+dy*dy;if(r[a]*r[a]>=dis)return true;elsereturn false;   
}
void bfs(int node)
{int temp;for(int i=head[node];i!=-1;i=edge[i].next){temp=edge[i].to;if(con[node][temp]&&con[temp][node]&&val[temp]){val[node]=val[temp];return; } }while(!Q.empty())Q.pop();Q.push(node);vis[node]=1;while(!Q.empty()){int now=Q.front();Q.pop();val[node]+=c[now];for(int i=head[now];i!=-1;i=edge[i].next){temp=edge[i].to;if(vis[temp]==0){vis[temp]=1;Q.push(temp);}}}   
}
int main()
{int t;int cas=0;scanf("%d",&t);while(t--){cnt=0;memset(head,-1,sizeof(head));memset(con,0,sizeof(con));memset(val,0,sizeof(val));int n;scanf("%d",&n); for(int i=0;i<n;i++){scanf("%d%d%d%d",&x[i],&y[i],&r[i],&c[i]);}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(canboom(i,j)&&i!=j){add(i,j,1);con[i][j]=1;}} }long long _max=-1;for(int i=0;i<n;i++){memset(vis,0,sizeof(vis));bfs(i);}for(int i=0;i<n;i++){_max=max(_max,val[i]);}//cout<<_max<<endl;printf("Case #%d: %lld\n",++cas,_max);}
}

这篇关于点炸弹(bfs+剪枝，或链式向前星+剪枝+bfs)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---