USACO 669 MOOCAST AC代碼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1001;
const int MAXV=25000;
vector< vector<int> > net(MAXN);
int raw[MAXN][2];
int n;
int goDFS(int begin){
? ? stack<int> s;
? ? vector<bool> vis(n+1);
? ? int count=0;
? ? s.push(begin);
? ? vis[begin]=true;
? ? count++;? ??
? ? while(s.size()>0){
? ? ? ? int a=s.top();
? ? ? ? s.pop();
? ? ? ? for(int b :net[a]){
? ? ? ? ? ? if(!vis[b]){
? ? ? ? ? ? ? ? s.push(b);
? ? ? ? ? ? ? ? vis[b]=true;
? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? }? ??
? ? ? ? }? ??
? ? }
? ? return count;
}
bool connected(ll m){
? ? //clear existing graph
? ? for(int i=1;i<=n;i++){
? ? ? ? net[i].clear();
? ? }? ??
? ? //construct graph
? ? for(int i=1;i<=n-1;i++){
? ? ? ? for(int j=i+1;j<=n;j++){
? ? ? ? ? ? int dx=raw[i][0]-raw[j][0];
? ? ? ? ? ? int dy=raw[i][1]-raw[j][1];
? ? ? ? ? ? if(dx*dx+dy*dy<=m){
? ? ? ? ? ? ? ? net[i].push_back(j);
? ? ? ? ? ? ? ? net[j].push_back(i);
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? //dfs to check if connected
? ? if(goDFS(1)<n){
? ? ? ? return false;
? ? }else{
? ? ? ? return true;
? ? }
}? ??
int main()
{
? ? ifstream inf("moocast.in");
? ? ofstream outf("moocast.out");
? ? inf>>n;
? ? for(int i=1;i<=n;i++){
? ? ? ? inf>>raw[i][0]>>raw[i][1];
? ? }
? ? //binary search
? ? ll l=0, r=MAXV*MAXV+MAXV*MAXV,res=0;
? ? while(l<=r){
? ? ? ? ll m=(l+r)/2;
? ? ? ? if(connected(m)){
? ? ? ? ? ? res=m;
? ? ? ? ? ? r=m-1;
? ? ? ? }else{
? ? ? ? ? ? l=m+1;
? ? ? ? }
? ? }? ??
? ? outf<<res<<endl;
? ? inf.close();
? ? outf.close();
? ? return 0;
}
