POJ经典算法题.docxVIP

最优连通子集Description(poj1192)众所周知，我们可以通过直角坐标系把平面上的任何一个点P用一个有序数对(x, y)来唯一表示，如果x, y都是整数，我们就把点P称为整点，否则点P称为非整点。我们把平面上所有整点构成的集合记为W。?定义1 两个整点P1(x1, y1), P2(x2, y2)，若|x1-x2| + |y1-y2| = 1，则称P1, P2相邻，记作P1~P2，否则称P1, P2不相邻。?定义 2 设点集S是W的一个有限子集，即S = {P1, P2,..., Pn}(n = 1)，其中Pi(1 = i = n)属于W，我们把S称为整点集。?定义 3 设S是一个整点集，若点R, T属于S，且存在一个有限的点序列Q1, Q2, ?, Qk满足:?1. Qi属于S（1 = i = k）;?2. Q1 = R, Qk = T;?3. Qi~Qi + 1(1 = i = k-1)，即Qi与Qi + 1相邻;?4. 对于任何1 = i j = k有Qi ≠ Qj;?我们则称点R与点T在整点集S上连通，把点序列Q1, Q2,..., Qk称为整点集S中连接点R与点T的一条道路。?定义4 若整点集V满足：对于V中的任何两个整点，V中有且仅有一条连接这两点的道路，则V称为单整点集。?定义5 对于平面上的每一个整点，我们可以赋予它一个整数，作为该点的权，于是我们把一个整点集中所有点的权的总和称为该整点集的权和。?我们希望对于给定的一个单整点集V，求出一个V的最优连通子集B，满足：?1. B是V的子集?2. 对于B中的任何两个整点，在B中连通；?3. B是满足条件(1)和(2)的所有整点集中权和最大的。?Input第1行是一个整数N（2 = N = 1000），表示单整点集V中点的个数；?以下N行中，第i行(1 = i = N)有三个整数，Xi, Yi, Ci依次表示第i个点的横坐标，纵坐标和权。同一行相邻两数之间用一个空格分隔。-10^6 = Xi, Yi = 10^6；-100 = Ci = 100。?Output仅一个整数，表示所求最优连通集的权和。Sample Input50 0 -20 1 11 0 10 -1 1-1 0 1Sample Output2import java.util.Scanner;public class Main { static int n; static int x[]; static int y[]; static int c[]; static int ans=0;static int search(int i,int parent){ int ret=0,t; for(int j=0;j n;j++) { if(parent!=jMath.abs(x[i]-x[j])+Math.abs(y[i]-y[j])==1) { t=search(j,i); if(t0)ret+=t; } } if(ret+c[i]ans)ans=ret+c[i]; return ret+c[i];}public static void main(String[] args) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); x=new int[n]; y=new int[n]; c=new int[n]; for(int i=0;i n;i++){ x[i]=sc.nextInt(); y[i]=sc.nextInt(); c[i]=sc.nextInt(); } search(0,-1); System.out.println(ans); }}陨石的秘密Description(poj1187)公元11380年，一颗巨大的陨石坠落在南极。于是，灾难降临了，地球上出现了一系列反常的现象。当人们焦急万分的时候，一支中国科学家组成的南极考察队赶到了出事地点。经过一番侦察，科学家们发现陨石上刻有若干行密文，每一行都包含5个整数：?1 1 1 1 6?0 0 6 3 57?8 0 11 3 2845?著名的科学家SS发现，这些密文实际上是一种复杂运算的结果。为了便于大家理解这种运算，他定义了一种SS表达式：?1． SS表达式是仅由{，}，[，]，（，）组成的字符串。?2． 一个空串是SS表达式。?3． 如果A是SS表达式，且A中不含字符{，}，[，]，则(A)是SS表达式。?4． 如果A是SS表达式，且A中不含字符{，}，则[A]是SS表达式。?5． 如果A是SS表达式，则{A}是SS表达式。?6． 如果A和B都是SS表达式，则AB也是SS表达式。?例如?()(())[]?{()[()]}?{{[[(())]]}}?都是SS表达式。?而?()(