作者存档：edward_mj

【题目大意】

定义点与点之间的距离为max(|Xi-Xj|,|Yi-Yj|)

给定N个点，将这N个点中每个点与最近点的距离加起来，输出SUM。

【算法分析】

算法1：

算了下复杂度O(N^2)的话加些优化应该可以卡过。

于是我把他们按x排序，x相等的按y排序。

然后枚举当前点i，并向前和向后枚举点j，如果出现abs(X[j]-X[i])>=now （其它now为当前答案），那么可以break退出循环。（最优化剪枝）

然后这样就可以9000MS左右AC了。

算法2：

同算法1那样排序。

再按X坐标离散化。

然后枚举当前点i，并二分答案（当前最短距离）。

问题转化为看是否存在点(X[j],Y[j])，使得abs(X[j]-X[i])<=ANS 且 abs(Y[j]-Y[i])<=ANS

于是就可以以X轴为线段树所划分的区间建立一棵线段树，线段树上再建立一棵以Y坐标为key值的平衡树。

然后在上面进行查找。每次查找的复杂度是O((lgN)^2)。

加上二分答案，每个点的处理复杂度为O((lgN)^3)。

所以总时间复杂度为O(N (lgN)^3 )。

空间复杂度为O(NlgN)。

因为最同一深度的线段树区间下，一个点只能出现在一个区间内。所以一个点最多出现lgN次。所以空间复杂度不是问题。

但是这个算法编程复杂度可能比较高。如果用STL的

【其它】由于我不会STL，所以算法2就不写了。。。

【CODE】

#include #include #include #include #include using namespace std;
const int N=101111;
const int INF=0x7FFFFFFF;
int n;
struct type{int x,y;}L[N];
long long ans;

inline bool cmp(type x,type y){
    if (x.x    if (x.x>y.x) return false;
    if (x.y    return false;
}   

void input(){
    for (int i=1;i<=n;i++)
      scanf("%d%d",&L[i].x,&L[i].y);
    sort(&L[1],&L[n+1],cmp);
}   

void work(){
    ans=0;
    int i,j,now;
    for (i=1;i<=n;i++){
        now=INF;
       
        j=i-1;
        while (j){
            if (L[i].x-L[j].x>=now) break;
            now            j–;
        }   

        j=i+1;
        while (j<=n){
            if (L[j].x-L[i].x>=now) break;
            now            j++;
        }   
       
        ans+=now;
    }   
    cout << ans << endl;
}   

int main(){
    while (scanf("%d",&n)!=EOF){
        input();
        work();
    }   
}   

【题目大意】

有点已经成一个块了，让你加最少费用的边，使得它整个图成为一个连通块。

【算法分析】

经典最小生成树。

用并差集处理块，然后排序一下搞个kruskal。

但是很容易TLE。于是我加了那个启发式合并。

【其它】

尽管如此，我用G++交还是TLE,C++500多MS。

可能并差集写成非递归会好点。

【CODE】

#include #include #include #include #include #include using namespace std;
const int N=1000000;
int Tc,n,m,k,done,ans;
int f[N],d[N][3];
int num[N];

int gf(int p){
    if (f[p]==p) return p;
    f[p]=gf(f[p]);
    return f[p];
}

void input(){
    done=0; ans=0;
    int i,j,t,one,x;
    scanf("%d%d%d",&n,&m,&k);
    for (i=1;i<=n;i++){
        f[i]=i;
        num[i]=1;
    }
    for (i=1;i<=m;i++)
      scanf("%d%d%d",&d[i][0],&d[i][1],&d[i][2]);
    for (i=1;i<=k;i++){
        scanf("%d%d",&t,&one);
        for (j=1;j          scanf("%d",&x);
          if (gf(x)!=gf(one)){
            if (num[f[x]]                num[f[one]]+=num[f[x]];
                f[f[x]]=f[one];
            }
            else{
                num[f[x]]+=num[f[one]];
                f[f[one]]=f[x];
            }
            done++;
          }
        }
    }
}

int cmp(const void *x,const void *y){
    return ((int *)x)[2]-((int *)y)[2];
}

void work(){
    if (done==n-1) return;
    qsort(d[1],m,sizeof(int)*3,cmp);
    for (int i=1;i<=m;i++){
      int &x=d[i][0],&y=d[i][1];
      if (gf(x)!=gf(y)){
          if (num[f[x]]              num[f[y]]+=num[f[x]];
              f[f[x]]=f[y];
          }
          else{
              num[f[x]]+=num[f[y]];
              f[f[y]]=f[x];
          }

          done++;
          ans+=d[i][2];
          if (done==n-1) return;
      }
    }
}

void output(){
    if (done==n-1) printf("%dn",ans);
              else printf("-1n");
}

int main(){
    cin >> Tc;
    for (int i=1;i<=Tc;i++){
        input();
        work();
        output();
    }
}