주소:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3016
제목:n 개의 선분 을 드 리 겠 습 니 다.이 선분 들 은 모두 좌표 축 과 평행 하고 선분 이 겹 치지 않 지만 교점 이 있 습 니 다.모든 선분 을 자 르 는 데 값 이 있 습 니 다.현재 이 선분 들 은 폐쇄 된 구간 을 형성 하고 있 습 니 다.어떻게 자 르 는 지 물 어보 면 모든 점 사이 에 통로 가 있 고 비용 이 가장 적 습 니 다.
분석:이 문 제 는 선분 의 껍질 을 버 리 면 모든 칸 이 하나의 점 이 고 바깥 의 평면 은 하나의 점 이 며 점 사이 의 변 은 바로 선분 을 자 르 는 비용 이 고 답 은 가장 작은 생 성 나무의 값 이 분명 하 다.그런데 이 라인 들 을 어떻게 작은 칸 으로 처리 해 야 할 지 머리 가 아파 요.×m 개의 격자,격자 사이 의 가장자리 가 하나의 라인 이 라면 값 은 절단 라인 의 값 입 니 다.만약 에 라인 이 없 으 면 값 이 0 입 니 다.지금 은 사 이 드 를 만 드 는 것 이 간단 합 니 다.각 칸 의 상하 좌우 사 이 드 를 만 들 면 됩 니 다.그리고 하하,코드 를 구체 적 으로~~
코드:
/** head files*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
/** some operate*/
#define REP(i,n) for(int i=0;i=(l);--i)
#define foreach(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
#define CLR(arr) memset(arr,0,sizeof(arr))
#define MAX3(a,b,c) max(a,max(b,c))
#define MAX4(a,b,c,d) max(max(a,b),max(c,d))
#define MIN3(a,b,c) min(a,min(b,c))
#define MIN4(a,b,c,d) min(min(a,b),min(c,d))
/** some const*/
#define N 1210
#define M N*N
#define PI acos(-1.0)
#define oo 1000000000
#define loo 1000000000000000000LL
#define eps 1e-8
/** some alias*/
typedef long long LL;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
/** Global variables*/
/** some template names, just push ctrl+j to get it in*/
//getint
//manacher
//pqueue
//combk n m
//pmatrix n
//suffixarray
//sbtree
struct seg
{
int x1,y1,x2,y2,c;
void rd()
{
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
}
};
struct Node
{
int v,c;
Node(){}
Node(int v, int c):v(v),c(c){}
bool operatora.c;
}
};
vector gx;
vector gy;
seg sg[N];
int g[N][N];
vector e[M];
bool vis[M];
priority_queue pq;
int no(int i, int j)
{
return g[i*2][j*2];
}
void addedge(int u, int v, int c)
{
e[u].push_back(Node(v,c));
e[v].push_back(Node(u,c));
}
LL solve()
{
while(!pq.empty())pq.pop();
LL ret=0;
for(pq.push(Node(0,0));!pq.empty();)
{
Node now=pq.top();
pq.pop();
if(vis[now.v])continue;
ret=ret+now.c;
foreach(it,e[now.v])
if(!vis[it->v])pq.push(*it);
vis[now.v]=1;
}
return ret;
}
int main()
{
freopen("a","r",stdin);
//freopen("wa","w",stdout);
int n,m,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
gx.clear();
gy.clear();
REP(i,n)
{
sg[i].rd();
gx.push_back(sg[i].x1);
gx.push_back(sg[i].x2);
gy.push_back(sg[i].y1);
gy.push_back(sg[i].y2);
if(sg[i].x1>sg[i].x2)swap(sg[i].x1,sg[i].x2);
if(sg[i].y1>sg[i].y2)swap(sg[i].y1,sg[i].y2);
}
sort(gx.begin(),gx.end());
sort(gy.begin(),gy.end());
gx.resize(unique(gx.begin(),gx.end())-gx.begin());
gy.resize(unique(gy.begin(),gy.end())-gy.begin());
CLR(g);
unsigned xi,yi;
REP(i,n)
{
xi=lower_bound(gx.begin(),gx.end(),sg[i].x1)-gx.begin();
yi=lower_bound(gy.begin(),gy.end(),sg[i].y1)-gy.begin();
if(sg[i].x1sg[i].x2)break;
g[xi*2][yi*2+1]=sg[i].c;
}
}
else if(sg[i].y1sg[i].y2)break;
g[xi*2+1][yi*2]=sg[i].c;
}
}
}
m=0;
for(xi=1;xi
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1874: 원활 한 공사 계속 [Dijkstra & SPFA & Floyd]
모 성 은 여러 해 동안 의 원활 한 공사 계획 을 실행 한 후에 마침내 많은 길 을 건설 하 였 다.길 을 많이 건 너 지 않 아 도 좋 지 않다.
한 도시 에서 다른 도시 로 갈 때마다 여러 가지 도로 방안 을 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
