UVALive-3662(맨해튼 거리, MST)

17618 단어
2015-04-30 14:37:52
제목: 누드문제, 그런데 포제이의 프로그램이 붙어있는데 넘을 수가 없어...자세한 오류를 발견했습니다: int sz = unique (a + 1, a + n + 1) - a - 1;마지막 그거. - 잃어버리면 안 돼.
  1 #include 
  2 #include 
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  7 #include <set>
  8 #include 
  9 #include 
 10 #include <string>
 11 #include 
 12 #include 
 13 using namespace std;
 14 
 15 #define MEM(a,b) memset(a,b,sizeof(a))
 16 #define REP(i,n) for(int i=0;i 17 #define FOR(i,a,b) for(int i=(a);i<=(b);++i)
 18 #define getmid(l,r) ((l) + ((r) - (l)) / 2)
 19 #define MP(a,b) make_pair(a,b)
 20 #define PB(a) push_back(a)
 21 
 22 typedef long long ll;
 23 typedef pair<int,int> pii;
 24 const double eps = 1e-8;
 25 const int INF = (1 << 30) - 1;
 26 const int MAXN = 100010;
 27 
 28 int N,ecnt;
 29 int fa[MAXN],A[MAXN],B[MAXN];
 30 
 31 struct edge{
 32     int u,v,c;
 33     bool operator < (const edge a) const{
 34         return c < a.c;
 35     }
 36 }e[4 * MAXN];
 37 
 38 void Add_edge(int u,int v,int c){
 39     e[++ecnt].u = u;
 40     e[ecnt].v = v;
 41     e[ecnt].c = c;
 42 }
 43 
 44 struct Node{
 45     int x,y,id;
 46     bool operator < (const Node a) const{
 47         return x == a.x ? y < a.y : x < a.x;
 48     }
 49 }p[MAXN];
 50 
 51 struct BIT{
 52     int c[MAXN],ps[MAXN],tmax;
 53     void init(int tmp){
 54         tmax = tmp;
 55         FOR(i,1,tmax) c[i] = INF;
 56         MEM(ps,-1);
 57     }
 58     int lowbit(int x){ return x & (-x); }
 59     void update(int x,int d,int pos){
 60         while(x){
 61             if(d < c[x]){
 62                 c[x] = d;
 63                 ps[x] = pos;
 64             }
 65             x -= lowbit(x);
 66         }
 67     }
 68     int get(int x){
 69         int res = INF,pos = -1;
 70         while(x <= tmax){
 71             if(c[x] < res){
 72                 res = c[x];
 73                 pos = ps[x];
 74             }
 75             x += lowbit(x);
 76         }
 77         return pos;
 78     }
 79 }bit;
 80 
 81 int Dis(int a,int b){ return abs(p[a].x - p[b].x) + abs(p[a].y - p[b].y); }
 82 int Find(int x){ return fa[x] == x ? x : fa[x] = Find(fa[x]); }
 83 
 84 ll Manhattan_mst(){
 85     for(int dir = 1; dir <= 4; ++dir){
 86         //    ：(1) none , (2) y=x , (3) y=0 , (4) y=x
 87         if(dir == 2 || dir == 4)
 88             FOR(i,1,N) swap(p[i].x,p[i].y);
 89         else if(dir == 3)
 90             FOR(i,1,N) p[i].y = -p[i].y;
 91         sort(p + 1,p + N + 1); //sort by x
 92         FOR(i,1,N) A[i] = B[i] = p[i].y - p[i].x; //   
 93         sort(B + 1,B + N + 1);
 94         int sz = unique(B + 1,B + N + 1) - B - 1;
 95         //        
 96         bit.init(sz);
 97         for(int i = N; i >= 1; --i){ //  x       
 98             int pos = lower_bound(B + 1,B + sz + 1,A[i]) - B;
 99             int ans = bit.get(pos); //    y-x      x+y   
100             if(ans != -1) Add_edge(p[i].id,p[ans].id,Dis(i,ans));//i    ans
101             bit.update(pos,p[i].x + p[i].y,i);
102         }
103     }
104     //Kruskal
105     ll res = 0;
106     sort(e + 1,e + ecnt + 1);
107     FOR(i,1,N) fa[i] = i;
108     FOR(i,1,ecnt){
109         int x = Find(e[i].u);
110         int y = Find(e[i].v);
111         if(x != y){
112             fa[y] = x;
113             res += (ll)e[i].c;
114         }
115     }
116     return res;
117 }
118 
119 int main(){
120     int  tt = 0;
121     while(scanf("%d",&N) != EOF && N){
122         FOR(i,1,N){
123             scanf("%d%d",&p[i].x,&p[i].y);
124             p[i].id = i;
125         }
126         ecnt = 0;
127         printf("Case %d: Total Weight = ",++tt);
128         printf("%lld
",Manhattan_mst());
129     }
130     return 0;
131 }

 
전재 대상:https://www.cnblogs.com/naturepengchen/articles/4468863.html
[C++] BAEKJOON 1920
47. Express -2

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage