本文主要是介绍2011 Multi-University Training Contest 1 - Host by HNUEarth Hour，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题木想到竟然可以转发为最短路问题，，让我纠结了近一个下午，，更悲剧的是spfa竟然写错了，，，下面说一下题意，就是在世界日这一天里为了响应号召某大学决定关掉除到图书馆，自习室，寝室的路灯，最后问最多可以关多少路灯，，思路：根据路灯的照射范围判断两个地方是不是相通如果相通就连成边同时把边权设置为1，然后求3次最短路径，，再枚举各个点找到dis1[i]+dis2[i]+dis3[i]最小的那个从而得出最多可以关的路灯。。。
AC代码：
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<vector>
#define N 201
#define M 0xfffffff
using namespace std;
typedef struct
{ int x;int y;int r;
}Point;
typedef struct
{ int v;int len;
}Node;
vector<Node> map[N];
Point t[N];
int dis1[N],dis2[N],dis3[N];
bool visit[N];
int n,i,j;
int max(int a,int b)
{if(a>b) return a;else return b;
}
void spfa(int s,int dis[])
{ memset(visit,false,sizeof(visit));for(i=0;i<n;++i)dis[i]=M;dis[s]=0;visit[s]=true;queue<int>Q;Q.push(s);while(!Q.empty()){ int now=Q.front();Q.pop();visit[now]=false;int len=map[now].size();for(i=0;i<len;++i)if(dis[map[now][i].v]>map[now][i].len+dis[now]){ dis[map[now][i].v]=map[now][i].len+dis[now];if(!visit[map[now][i].v]){Q.push(map[now][i].v);visit[map[now][i].v]=true;}}}
}
int main()
{ int Case;cin>>Case;while(Case--){ cin>>n;for(i=0;i<n;++i)map[i].clear();for(i=0;i<n;++i)cin>>t[i].x>>t[i].y>>t[i].r;for(i=0;i<n-1;++i)for(j=i+1;j<n;++j){ Node p;int s1=(t[i].x-t[j].x)*(t[i].x-t[j].x)+(t[i].y-t[j].y)*(t[i].y-t[j].y);int s2=(t[i].r+t[j].r)*(t[i].r+t[j].r);if(s1<=s2){ p.v=j;p.len=1;map[i].push_back(p);p.v=i;map[j].push_back(p);}}spfa(0,dis1);spfa(1,dis2);spfa(2,dis3);int ans=-1;for(i=0;i<n;++i)if(dis1[i]<M&&dis2[i]<M&&dis3[i]<M)ans=max(ans,n-(dis1[i]+dis2[i]+dis3[i]+1));cout<<ans<<endl;}return 0;}
这篇关于2011 Multi-University Training Contest 1 - Host by HNUEarth Hour的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
