2011-09-11 08:50:11Morris
b174. 旅游规划
b174. 旅游规划
/**********************************************************************************/
/* Problem: b174 "旅游规划" from 2008 海峽兩岸青少年程式設計競賽*/
/* Language: C */
/* Result: AC(74ms, 7.3MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-11 08:36:25 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
#define oo 2147483647
#define Swap(x, y) {int t; t = x, x = y, y = t;}
struct {
int x, y;
}link[400001], X[400001];
void Merge(int l, int m, int h) {
int in1 = l, in2 = m+1;
int i, j, Top = 0;
while(in1 <= m && in2 <= h) {
if(link[in1].x < link[in2].x ||
(link[in1].x == link[in2].x && link[in1].y < link[in2].y))
X[Top++] = link[in1++];
else
X[Top++] = link[in2++];
}
while(in1 <= m) X[Top++] = link[in1++];
while(in2 <= h) X[Top++] = link[in2++];
for(i = 0, j = l; i < Top; i++, j++)
link[j] = X[i];
}
void MergeSort(int l, int h) {
if(l < h) {
int m = (l + h)/2;
MergeSort(l, m);
MergeSort(m+1, h);
Merge(l, m, h);
}
}
int min(int x, int y) {
return x < y ? x : y;
}
int max(int x, int y) {
return x > y ? x : y;
}
int NodeT[200000], NodeL[200000];
int Parent[200000], Queue[200000], Used[200000];
int Down[200000][2], Up[200000];
int DownNode[200000][2];
void Solve(int n) {
int i, j, k, Qt = -1, tn, tL;
memset(Used, 0, sizeof(Used));
memset(Down, 0, sizeof(Down));
memset(Up, 0, sizeof(Up));
Queue[++Qt] = 0, Used[0] = 1, Parent[0] = -1;
for(i = 0; i < n; i++) {
if(NodeT[i] == 1)
Down[i][0] = 1;
Parent[i] = -1;
}
for(i = 0; i <= Qt; i++) {
tn = Queue[i];
for(j = NodeL[tn], k = 0; k < NodeT[tn]; j++, k++) {
if(link[j].y != Parent[tn]) {
if(Used[link[j].y] == 0) {
Used[link[j].y] = 1;
Queue[++Qt] = link[j].y;
Parent[link[j].y] = tn;
}
}
}
}
for(i = Qt; i >= 0; i--) {
tn = Queue[i];
for(j = NodeL[tn], k = 0; k < NodeT[tn]; j++, k++) {
if(link[j].y != Parent[tn]) {
tL = Down[link[j].y][0]+1;
if(tL > Down[tn][1]) {
Swap(tL, Down[tn][1]);
DownNode[tn][1] = link[j].y;
}
if(Down[tn][0] < Down[tn][1]) {
Swap(Down[tn][0], Down[tn][1]);
Swap(DownNode[tn][0], DownNode[tn][1]);
}
}
}
}
for(i = 0; i <= Qt; i++) {
tn = Queue[i];
for(j = NodeL[tn], k = 0; k < NodeT[tn]; j++, k++) {
if(link[j].y != Parent[tn]) {
tL = Down[tn][0];
if(DownNode[tn][0] == link[j].y)
tL = Down[tn][1];
tL = max(Up[tn]+1, tL);
Up[link[j].y] = max(tL, Up[link[j].y]);
}
}
}
/*Reuse NodeT[]*/
int maxL = 0;
for(i = 0; i < n; i++) {
NodeT[i] = max(Down[i][0]+Down[i][1]-1, Down[i][0]+Up[i]);
maxL = max(maxL, NodeT[i]);
}
for(i = 0; i < n; i++)
if(maxL == NodeT[i])
printf("%d\n", i);
}
main() {
int n, m, i, j;
while(scanf("%d", &n) == 1) {
for(i = 0; i < n-1; i++) {
scanf("%d %d", &link[i].x, &link[i].y);
link[n-1+i].x = link[i].y, link[n-1+i].y = link[i].x;
}
m = n*2-3;
MergeSort(0, m);
for(i = 0; i < n; i++)
NodeT[i] = 0, NodeL[i] = oo;
for(i = 0; i <= m; i++) {
NodeL[link[i].x] = min(NodeL[link[i].x], i);
NodeT[link[i].x]++;
}
Solve(n);
}
return 0;
}
內容 ：
W市的交通规划出现了重大问题，市政府下决心在全市的各大交通路口安排交通疏导员来疏导密集的车流。但由于人员不足，W市市长决定只在最需要安排人员的路口安放人员。具体说来，W市的交通网络十分简单，它包括n个交叉路口和n-1条街道，任意一条街道连接两个交叉路口，并且任意两个交叉路口之间都存在一条路径互相连接。经过长期调查结果显示如果一个交叉路口位于W市交通网的最长路径上，那么这个路口必然拥挤不堪，所谓最长路径定义为某条路径p=(v1,v2,v3…vk)，路径经过的路口各不相同且城市中不存在长度>k的路径（因此可能存在着不唯一的最长路径）。因此W市市长希望知道有哪些路口位于城市交通网的最长路径之上。
輸入說明
：
第一行包括一个整数n。
之后的n-1行每行包括两个整数u, v表示编号为u和v的路口之间存在着一条街道（注意：路口被依次编号为0到n-1）
輸出說明
：
输出包括若干行，每行包括一个整数——某个位于最长路上路口的编号。
为了确保解唯一，我们规定位于所有最长路上的路口按编号顺序从小到大输出。
範例輸入 ：
10 0 1 0 2 0 4 0 6 0 7 1 3 2 5 4 8 6 9
範例輸出 ：
0 1 2 3 4 5 6 8 9
提示
：
说明：
这里存在着若干条最长路径，其中的两条是3-1-0-2-5与8-4-0-6-9，他们的长度都是5，但是不存在长度>5的路径且所有最长路径都不包括路口7，所以答案中没有7。
数据范围：
对于50%的数据保证n<=1000
对于100%的数据保证n<=200000
这里存在着若干条最长路径，其中的两条是3-1-0-2-5与8-4-0-6-9，他们的长度都是5，但是不存在长度>5的路径且所有最长路径都不包括路口7，所以答案中没有7。
数据范围：
对于50%的数据保证n<=1000
对于100%的数据保证n<=200000
出處
：
2008 海峽兩岸青少年程式設計競賽
作法 : 這應該就是所謂的樹形DP
先將給的圖形, 整理成一棵樹, 接下來用 BFS 拓展出深度,
從最深的開始倒退回去, 開始更新, 來是子樹的最長路徑 (必須紀錄兩個最長路徑)
接著, 再從深度最小的開始, 更新來自其他部分的最長路徑,
由父節點的父節點拉下來的最長路徑, or 來自父節點的子節點的最長路徑
來自父節點的子節點的最長路徑 => 直接用"父節點"子樹的最長路徑,
由於可能會重複(也就是是本身的那個), 所以才要紀錄兩條最長路徑
作法 : 這應該就是所謂的樹形DP
先將給的圖形, 整理成一棵樹, 接下來用 BFS 拓展出深度,
從最深的開始倒退回去, 開始更新, 來是子樹的最長路徑 (必須紀錄兩個最長路徑)
接著, 再從深度最小的開始, 更新來自其他部分的最長路徑,
由父節點的父節點拉下來的最長路徑, or 來自父節點的子節點的最長路徑
來自父節點的子節點的最長路徑 => 直接用"父節點"子樹的最長路徑,
由於可能會重複(也就是是本身的那個), 所以才要紀錄兩條最長路徑
/**********************************************************************************/
/* Problem: b174 "旅游规划" from 2008 海峽兩岸青少年程式設計競賽*/
/* Language: C */
/* Result: AC(74ms, 7.3MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-11 08:36:25 */
/**********************************************************************************/
#include<stdio.h>
#include<string.h>
#define oo 2147483647
#define Swap(x, y) {int t; t = x, x = y, y = t;}
struct {
int x, y;
}link[400001], X[400001];
void Merge(int l, int m, int h) {
int in1 = l, in2 = m+1;
int i, j, Top = 0;
while(in1 <= m && in2 <= h) {
if(link[in1].x < link[in2].x ||
(link[in1].x == link[in2].x && link[in1].y < link[in2].y))
X[Top++] = link[in1++];
else
X[Top++] = link[in2++];
}
while(in1 <= m) X[Top++] = link[in1++];
while(in2 <= h) X[Top++] = link[in2++];
for(i = 0, j = l; i < Top; i++, j++)
link[j] = X[i];
}
void MergeSort(int l, int h) {
if(l < h) {
int m = (l + h)/2;
MergeSort(l, m);
MergeSort(m+1, h);
Merge(l, m, h);
}
}
int min(int x, int y) {
return x < y ? x : y;
}
int max(int x, int y) {
return x > y ? x : y;
}
int NodeT[200000], NodeL[200000];
int Parent[200000], Queue[200000], Used[200000];
int Down[200000][2], Up[200000];
int DownNode[200000][2];
void Solve(int n) {
int i, j, k, Qt = -1, tn, tL;
memset(Used, 0, sizeof(Used));
memset(Down, 0, sizeof(Down));
memset(Up, 0, sizeof(Up));
Queue[++Qt] = 0, Used[0] = 1, Parent[0] = -1;
for(i = 0; i < n; i++) {
if(NodeT[i] == 1)
Down[i][0] = 1;
Parent[i] = -1;
}
for(i = 0; i <= Qt; i++) {
tn = Queue[i];
for(j = NodeL[tn], k = 0; k < NodeT[tn]; j++, k++) {
if(link[j].y != Parent[tn]) {
if(Used[link[j].y] == 0) {
Used[link[j].y] = 1;
Queue[++Qt] = link[j].y;
Parent[link[j].y] = tn;
}
}
}
}
for(i = Qt; i >= 0; i--) {
tn = Queue[i];
for(j = NodeL[tn], k = 0; k < NodeT[tn]; j++, k++) {
if(link[j].y != Parent[tn]) {
tL = Down[link[j].y][0]+1;
if(tL > Down[tn][1]) {
Swap(tL, Down[tn][1]);
DownNode[tn][1] = link[j].y;
}
if(Down[tn][0] < Down[tn][1]) {
Swap(Down[tn][0], Down[tn][1]);
Swap(DownNode[tn][0], DownNode[tn][1]);
}
}
}
}
for(i = 0; i <= Qt; i++) {
tn = Queue[i];
for(j = NodeL[tn], k = 0; k < NodeT[tn]; j++, k++) {
if(link[j].y != Parent[tn]) {
tL = Down[tn][0];
if(DownNode[tn][0] == link[j].y)
tL = Down[tn][1];
tL = max(Up[tn]+1, tL);
Up[link[j].y] = max(tL, Up[link[j].y]);
}
}
}
/*Reuse NodeT[]*/
int maxL = 0;
for(i = 0; i < n; i++) {
NodeT[i] = max(Down[i][0]+Down[i][1]-1, Down[i][0]+Up[i]);
maxL = max(maxL, NodeT[i]);
}
for(i = 0; i < n; i++)
if(maxL == NodeT[i])
printf("%d\n", i);
}
main() {
int n, m, i, j;
while(scanf("%d", &n) == 1) {
for(i = 0; i < n-1; i++) {
scanf("%d %d", &link[i].x, &link[i].y);
link[n-1+i].x = link[i].y, link[n-1+i].y = link[i].x;
}
m = n*2-3;
MergeSort(0, m);
for(i = 0; i < n; i++)
NodeT[i] = 0, NodeL[i] = oo;
for(i = 0; i <= m; i++) {
NodeL[link[i].x] = min(NodeL[link[i].x], i);
NodeT[link[i].x]++;
}
Solve(n);
}
return 0;
}
上一篇：b067. 6. 下棋問題