最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频

歡迎光臨散文網(wǎng) 會員登陸 & 注冊

USACO 669 MOOCAST AC代碼

2022-05-19 10:38 作者:信奧賽USACO鄭老師  | 我要投稿

#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;

}


USACO 669 MOOCAST AC代碼的評論 (共 條)

分享到微博請遵守國家法律
新河县| 大兴区| 洛隆县| 右玉县| 嘉鱼县| 那坡县| 宁城县| 庆阳市| 黄石市| 五指山市| 安宁市| 奉贤区| 灵武市| 新乡县| 始兴县| 潼南县| 和硕县| 滦南县| 类乌齐县| 武乡县| 盐城市| 临邑县| 岑溪市| 仁怀市| 措美县| 晋宁县| 唐河县| 建始县| 瑞安市| 海城市| 涞源县| 开化县| 昌江| 陆川县| 武功县| 平舆县| 赤城县| 丹阳市| 民乐县| 长垣县| 徐闻县|