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;

}