HDU/HDOJ 3832 Earth Hour
この問題は私が先に問題の意味をはっきり見なかった.2から3だと思った
結果は1,2,3でつながっているので、問題は明らかです.以前ジャンプボードの問題をしたことがあります.
これとよく似ています.
方法は,それぞれ1,2,3を単一ソース最短にし,ジャンプボードiを列挙することである.
dis 1[i]+dis 2[i]+dis 3[i]を最小にします.
そして処理すると本題の答えです
マイコード:
結果は1,2,3でつながっているので、問題は明らかです.以前ジャンプボードの問題をしたことがあります.
これとよく似ています.
方法は,それぞれ1,2,3を単一ソース最短にし,ジャンプボードiを列挙することである.
dis 1[i]+dis 2[i]+dis 3[i]を最小にします.
そして処理すると本題の答えです
マイコード:
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#define inf 99999999
using namespace std;
struct cir
{
int x;
int y;
int r;
};
struct node
{
int v;
int len;
};
vector<node>map[205];
int n;
void spfa(int s,int dis[])
{
int i,pre[205];
bool used[205];
queue<int>q;
memset(used,0,sizeof(used));
memset(pre,-1,sizeof(pre));
for(i=0;i<205;i++)
dis[i]=inf;
dis[s]=0;
used[s]=true;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
used[u]=false;
for(i=0;i<map[u].size();i++)
{
node p=map[u][i];
if(dis[p.v]>dis[u]+p.len)
{
dis[p.v]=dis[u]+p.len;
pre[p.v]=u;
if(!used[p.v])
{
used[p.v]=true;
q.push(p.v);
}
}
}
}
}
void init()
{
int i;
for(i=0;i<=n;i++)
map[i].clear();
}
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
int t,i,dist1,dist2,j,ans;
cir c[205];
node p;
int dis1[205],dis2[205],dis3[205];
scanf("%d",&t);
while(t--)
{
init();
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].r);
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
dist1=(c[i].x-c[j].x)*(c[i].x-c[j].x)+(c[i].y-c[j].y)*(c[i].y-c[j].y);
dist2=(c[i].r+c[j].r)*(c[i].r+c[j].r);
if(dist1<=dist2)
{
p.v=j;
p.len=1;
map[i].push_back(p);
p.v=i;
map[j].push_back(p);
}
}
}
spfa(1,dis1);
spfa(2,dis2);
spfa(3,dis3);
ans=-1;
for(i=1;i<=n;i++)
{
if(dis1[i]<inf&&dis2[i]<inf&&dis3[i]<inf)
ans=max(ans,n-(dis1[i]+dis2[i]+dis3[i]+1));
}
printf("%d
",ans);
}
return 0;
}