首页 > ACM题库 > HDU-杭电 > HDU 4663-Plane Partition-最小生成树-[解题报告]HOJ
2015
09-17

HDU 4663-Plane Partition-最小生成树-[解题报告]HOJ

Plane Partition

问题描述 :

A plane partition is a two-dimensional array of nonnegative integers ai,j (0<=i<n, 0<=j<m) that satisfies
1. 0<=ai,j<=p
2. ai,j>=ai,j+1
3. ai,j>=ai+1,j

In this problem, we add some additional constrains in the following form:
Given x, y, z, there exists some integer k (may be negative) such that ax+k,y+k=z+k.

Note: For i and j do not satisfy 0<=i<n and 0<=j<m, ai,j does not exist.

Count how many valid plane partitions are there.

输入:

First line, number of test cases, T.
Following are T test cases. For each test case, the first line contains four integers, n, m, p, t, where the last one is the number of additional constraints.
Following are t lines, each line contains three integers, x, y, z.

T<=200
1<=n,m,p<=7
0<=x,y,z<=7
It’s possible that there is no valid plane partitions.

输出:

First line, number of test cases, T.
Following are T test cases. For each test case, the first line contains four integers, n, m, p, t, where the last one is the number of additional constraints.
Following are t lines, each line contains three integers, x, y, z.

T<=200
1<=n,m,p<=7
0<=x,y,z<=7
It’s possible that there is no valid plane partitions.

样例输入:

2
1 1 1 0
1 1 1 1
1 1 1

样例输出:

2
1

题目:Outlets

题意:给定N个点,要将N个点用线段连接起来,其中给定的p,q两点必须用一条线段连接,要求在此限制下的最小生成树。

点个数也不多,纯粹当最小生成树算法练习。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 60;
int n, p, q, x[N], y[N];
double dist[N][N];
double cal(double dx,double dy){
    return sqrt(dx*dx + dy*dy);
}
bool done[N];
double d[N];
double solve(){
    memset(done,0,sizeof(done));
    double res = dist[p][q];
    done[p]=done[q]=1;
    for(int i=1; i<=n; i++){
        d[i] = min(dist[p][i], dist[q][i]);
    }
    for(int i=3; i<=n; i++){
        int j=-1;
        for(int k=1; k<=n; k++){
            if(done[k]) continue;
            if(j==-1 || d[k]<d[j])  j=k;
        }
        done[j]=1;
        res += d[j];
        for(int k=1; k<=n; k++){
            if(!done[k])    d[k] = min(d[k], dist[j][k]);
        }
    }
    return res;
}
int main(){
    while(~scanf("%d", &n) && n){
        scanf("%d %d", &p, &q);
        for(int i=1; i<=n; i++){
            scanf("%d %d", x+i, y+i);
            for(int j=1; j<i; j++){
                dist[i][j] = dist[j][i] = cal(x[i]-x[j], y[i]-y[j]);
            }
            dist[i][i]=0.0;
        }
        printf("%.2lf\n", solve());
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/hongrock/article/details/38878561