2019-2-2

//我的天第一次编写竟然这么长，一定有我没找到的方法，啊哈哈哈哈，
/* 北航机试2020/4/13 第二场第二题 */
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<iostream>
using namespace std;const int INF = 100000000;int input[100][4];
int n,computerId;typedef struct node
{
    int id;int type;int layer;//寻找祖先节点时，保存layer这个属性node* parent;node* port1;node* port2;node* port3;node* port4;
}Node,*Tree;Node* newNode(int id,int type)
{
    Node* temp = (Node*)malloc(sizeof(Node));temp->id = id;temp->type = type;temp->layer = 0;temp->parent = temp->port1 = temp->port2 = temp->port3 = temp->port4 = NULL;return temp;
}void createTree(Node* root)//根节点
{
    for(int i = 0;i<n;i++)//寻找父节点为root->id的孩子节点{
    if(input[i][2] == root->id){
    Node* temp = newNode(input[i][0],input[i][1]);temp->layer = root->layer + 1;temp->parent = root;//******节点之间的关系，将刚生成的temp和root关联if(root->type == 0)//if(temp->type == 0)错误，此外这条语句不写也没关系，下面匹配不到，会default选项{
    switch(input[i][3]){
    case 1:root->port1 = temp;break;case 2:root->port2 = temp;break;case 3:root->port3 = temp;break;case 4:root->port4 = temp;break;default:break;}createTree(temp);//递归建树，使用新生成的子节点建树}}}return ;
}/*
按照先序遍历的顺序存储打印机
*/
vector<Node*> printer;
void preOrder(Node* root)
{
    if(root){
    if(root->type == 2) printer.push_back(root);preOrder(root->port1);preOrder(root->port2);preOrder(root->port3);preOrder(root->port4);}
}Node* findChildPosition(Node* root,int id)
{
    if(root == NULL) return NULL;if(root->id == id) return root;Node *temp1,*temp2,*temp3,*temp4;temp1 = findChildPosition(root->port1,id);if(temp1)return temp1;temp2 = findChildPosition(root->port2,id);if(temp2)return temp2;temp3 = findChildPosition(root->port3,id);if(temp3)return temp3;temp4 = findChildPosition(root->port4,id);if(temp4)return temp4;return NULL;
}/* 通过寻找公共祖先节点计算最短距离 按照先序遍历的顺序不断更新printer，最后找到的最短的就是printer编号 */
//使用层数 + 父指针计算
Node* LeastCommonAncient(Node* root,int id1,int id2)
{
    Node* node1 = findChildPosition(root,id1);Node* node2 = findChildPosition(root,id2);int layer1 = node1->layer;int layer2 = node2->layer;if(layer1<layer2){
    int c = layer2-layer1;while(c--){
    node2 = node2->parent;}}if(layer1> layer2){
    int d = layer1 - layer2;while(d--){
    node1 = node1->parent;}}if(node1 == node2) return node1;while(node1->parent->id != node2->parent->id){
    node1 = node1->parent;node2 = node2->parent;}return node1->parent;//return node1;//错误写法
}int minDistance = INF;
int minDistanceId = 0;//最小的id是从1开始
//通过公共祖先节点，computerId和PrinterId得到最小的距离
int getMinDis(Node* node1,Node* ancient,Node* node2)
{
    int sum = 0;while(node1->parent != ancient){
    sum++;node1 = node1->parent;}sum++;while(node2->parent != ancient){
    sum++;node2 = node2->parent;}sum++;return sum;
}
//通过全局变量minDistance和minDistanceId
void getMinPrinterId(Node* root)
{
    Node *computer = findChildPosition(root,computerId);for(int i = 0;i<printer.size();i++){
    Node *node = findChildPosition(root,printer[i]->id);Node* ancient = LeastCommonAncient(root,computerId,printer[i]->id);int d = getMinDis(computer,ancient,node);//cout<<d<<endl;if(d<minDistance){
    minDistance = d;minDistanceId = printer[i]->id;}}
}vector<Node*> path;
void printUpToDown(Node* root,Node* temp)
{
    path.push_back(temp);while(temp->parent != root){
    path.push_back(temp);temp = temp->parent;}for(int i = path.size()-1;i>=0;i--){
    if(i == 0)cout<<path[i]->id<<endl;elsecout<<path[i]->id<<" ";}}void printDownToUp(Node* root,Node* temp)
{
    cout<<temp->id<<" ";while(temp->parent != root){
    cout<<temp->id<<" ";temp = temp->parent;}cout<<root->id<<" ";
}void print(Node* root)
{
    Node* node1 = findChildPosition(root,computerId);Node* node2 = findChildPosition(root,minDistanceId);Node* ancient = LeastCommonAncient(root,computerId,minDistanceId);printDownToUp(ancient,node1);printUpToDown(ancient,node2);
}int main()
{
    /*输入数据*/cin>>n;for(int i = 0;i<n;i++){
    cin>>input[i][0]>>input[i][1]>>input[i][2]>>input[i][3];}cin>>computerId;/*建树*///寻找根节点int i = 0;for(i = 0;i<n;i++){
    if(input[i][2] == 0)break;}//利用根节点建树Node* root = newNode(input[i][0],input[i][1]);root->layer = 1;createTree(root);preOrder(root);getMinPrinterId(root);cout<<minDistanceId<<endl;print(root);/*//TESTcout<<printer.size()<<endl;for(int i = 0;i<printer.size();i++){cout<<printer[i]->id<<" ";}cout<<endl;if(findChildPosition(root,9))cout<<findChildPosition(root,9)->id<<endl;elsecout<<"Not Find"<<endl;cout<<LeastCommonAncient(root,6,8)->id<<endl; */return 0;
}
/* IN: 8 1 0 0 0 2 0 1 1 3 0 1 2 4 0 1 3 5 1 4 3 6 1 3 1 7 2 3 2 8 2 3 3 6 OUT: 7 6 3 7 */

/* 2020/4/25 第二次编写 */
#include<stdio.h>
#include<vector>
#include<stdlib.h>
#include<algorithm>
using namespace std;int n,computerId;
int minStep = 1000000000;
int printerId;struct data
{
    int id;int type;int parent_id;int port;
}input[100];typedef struct node
{
    int id;int type;int layer;node* parent;node* port1;node* port2;node* port3;node* port4;
}Node,*Tree;Node* newNode(int id,int type)
{
    Node* temp = (Node*)malloc(sizeof(Node));temp->id = id;temp->type = type;temp->layer = 0;temp->parent = temp->port1 = temp->port2 = temp->port3 = temp->port4 = NULL;return temp;
}void createTree(Node* root)
{
    for(int i = 0;i<n;i++){
    if(input[i].parent_id == root->id){
    if(input[i].port == 1){
    Node* p1 = newNode(input[i].id,input[i].type);p1->layer = root->layer + 1;p1->parent = root;root->port1 = p1;createTree(p1);}if(input[i].port == 2){
    Node* p2 = newNode(input[i].id,input[i].type);p2->layer = root->layer + 1;p2->parent = root;root->port2 = p2;createTree(p2);}if(input[i].port == 3){
    Node* p3 = newNode(input[i].id,input[i].type);p3->layer = root->layer + 1;p3->parent = root;root->port3 = p3;createTree(p3);}if(input[i].port == 4){
    Node* p4 = newNode(input[i].id,input[i].type);p4->layer = root->layer + 1;p4->parent = root;root->port4 = p4;createTree(p4);}}}
}vector<Node*> preSqu;
void preOrder(Node* root)
{
    if(root){
    if(root->type == 2)preSqu.push_back(root);preOrder(root->port1);preOrder(root->port2);preOrder(root->port3);preOrder(root->port4);}
}Node* findChildPosition(int id,Node* root)
{
    if(root == NULL)return root;if(root->id == id)return root;/*//错误写法if(root->id == id)return root;if(root == NULL)return root;*/Node* port1 = findChildPosition(id,root->port1);if(port1) return port1;Node* port2 = findChildPosition(id,root->port2);if(port2) return port2;Node* port3 = findChildPosition(id,root->port3);if(port3) return port3;Node* port4 = findChildPosition(id,root->port4);if(port4) return port4;return NULL;
}Node* leastCommonAncient(Node* root,int id1,int id2)
{
    Node* temp1 = findChildPosition(id1,root);Node* temp2 = findChildPosition(id2,root);int layer1 = temp1->layer;int layer2 = temp2->layer;if(layer1> layer2){
    int t = layer1-layer2;while(t--){
    temp1 = temp1->parent;}}if(layer1<layer2){
    int t = layer2 - layer1;while(t--){
    temp2 = temp2->parent;}}if(temp1 == temp2) return temp1;while(temp1->parent!=temp2->parent){
    temp1 = temp1->parent;temp2 = temp2->parent;}return temp1->parent;
}void computerMinStep(Node* root)
{
    Node* computer = findChildPosition(computerId,root);for(int i = 0;i<preSqu.size();i++){
    Node* printer = findChildPosition(preSqu[i]->id,root);Node* ancient = leastCommonAncient(root,computer->id,printer->id);int step = computer->layer - ancient->layer + printer->layer - ancient->layer;if( step < minStep ){
    minStep = step;printerId = preSqu[i]->id;}}
}void printPath(Node* root)
{
    Node* computer = findChildPosition(computerId,root);Node* printer = findChildPosition(printerId,root);Node* ancient = leastCommonAncient(root,computer->id,printer->id);vector<Node*> up;vector<Node*> down;up.push_back(computer);while(computer->parent != ancient){
    up.push_back(computer);}down.push_back(printer);while(printer->parent!=ancient){
    down.push_back(printer);}down.push_back(ancient);for(int i = 0;i<up.size();i++){
    printf("%d ",up[i]->id);}for(int i = down.size()-1; i>=0 ; i--){
    if(i == 0)printf("%d\n",down[i]->id);elseprintf("%d ",down[i]->id);}
}int main()
{
    freopen("data.txt","r",stdin);scanf("%d",&n);for(int i = 0;i<n;i++){
    scanf("%d%d%d%d",&input[i].id,&input[i].type,&input[i].parent_id,&input[i].port);}scanf("%d",&computerId);Node* root = newNode(input[0].id,input[0].type);root->layer = 1;createTree(root);preOrder(root);computerMinStep(root);printf("%d\n",printerId);printPath(root);return 0;
}

/* 2020/4/27 第三次编写，代码精简一点 */
#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;struct data
{
    int id,type,parentId,port;
}input[100];
typedef struct node
{
    int id;int type;int layer;node* parent;node* port1;node* port2;node* port3;node* port4;
}Node,*Tree;int n;
int computerId;
int minSteps = 1000000000;
Node* printer = NULL;
Node* computer = NULL;Node* newNode(int id,int type)
{
    Node* temp = (Node*)malloc(sizeof(Node));temp->id = id;temp->type = type;temp->layer = 0;temp->parent = temp->port1 = temp->port2 = temp->port3 = temp->port4 = NULL;return temp;
}void createTree(Node* root)
{
    for(int i = 0;i<n;i++){
    if(input[i].parentId == root->id){
    Node* temp = newNode(input[i].id,input[i].type);temp->layer = root->layer + 1;temp->parent = root;switch(input[i].port){
    //注意在此处不能够定义语句case 1 :root->port1 = temp;break;case 2 :root->port2 = temp;break;case 3 :root->port3 = temp;break;case 4 :root->port4 = temp;break;default:break;}createTree(temp);}}
}vector<Node*> preOrderPrinter;
void preOrder(Node* root)
{
    if(root){
    if(root->type == 2){
    preOrderPrinter.push_back(root);}preOrder(root->port1);preOrder(root->port2);preOrder(root->port3);preOrder(root->port4);}
}Node* findChildPosition(Node* root,int id)
{
    if(root == NULL) return NULL;if(root->id == id) return root;Node* temp = findChildPosition(root->port1,id);if(temp) return temp;temp = findChildPosition(root->port2,id);if(temp) return temp;temp = findChildPosition(root->port3,id);if(temp) return temp;temp = findChildPosition(root->port4,id);if(temp) return temp;return NULL;
}Node* leastCommonAncient(Node* root,Node* temp1,Node* temp2)
{
    int layer1 = temp1->layer;int layer2 = temp2->layer;if(layer1>layer2){
    int t = layer1 - layer2;while(t--){
    temp1 = temp1->parent;}}if(layer1<layer2){
    int t = layer2 - layer1;while(t--){
    temp2 = temp2->parent;}}if(temp1 == temp2)return temp1;while(temp1->parent != temp2->parent){
    temp1 = temp1->parent;temp2 = temp2->parent;}return temp1->parent;
}int computeStep(Node* root,Node* temp1,Node* temp2)
{
    Node* ancient = leastCommonAncient(root,temp1,temp2);return temp1->layer-ancient->layer + temp2->layer - ancient->layer;
}void computeMinStep(Node* root)
{
    computer = findChildPosition(root,computerId);for(int i = 0;i<preOrderPrinter.size();i++){
    int step = computeStep(root,computer,preOrderPrinter[i]);if(step < minSteps){
    minSteps = step;printer = preOrderPrinter[i];}}
}void printPath(Node* root)
{
    vector<Node*> up,down;Node* ancient = leastCommonAncient(root,computer,printer);up.push_back(computer);computer = computer->parent;while(computer != ancient){
    up.push_back(computer);computer = computer->parent;}up.push_back(ancient);down.push_back(printer);printer = printer->parent;while(printer!=ancient){
    down.push_back(printer);printer = printer->parent;}for(int i = 0;i<up.size();i++){
    printf("%d ",up[i]->id);}for(int i = down.size()-1;i>=0;i--){
    if(i == 0)printf("%d\n",down[i]->id);elseprintf("%d ",down[i]->id);}
}int main()
{
    freopen("data.txt","r",stdin);scanf("%d",&n);for(int i = 0;i<n;i++){
    scanf("%d%d%d%d",&input[i].id,&input[i].type,&input[i].parentId,&input[i].port);}scanf("%d",&computerId);Node* root = newNode(input[0].id,input[0].type);root->layer = 1;createTree(root);preOrder(root);computeMinStep(root);printf("%d\n",printer->id);printPath(root);return 0;
}