C題

題目大意

題目鏈接
在公司中員工相互管理炒考，求某個員工最年輕的直接或者間接管理者。

分析

員工之間的相互管理可以看成一個有向圖穴墅，如果用一個鄰接矩陣來存儲的話會造成空間的浪費并且時間復雜度也會變高惶室，所以這里用鄰接表來存儲頂點之間的關系。在改變員工A,B的位置的時候先交換A,B員工所在矩陣的行（交換兩個人的管理者）玄货，再遍歷整個矩陣皇钞，如果有員工的管理者是A或者B就相互改變，簡而言之就是交換A誉结，B兩個人的管理者和手下鹅士。再來說說查詢年齡，這里用到dfs來搜索最小年齡惩坑，除了第一個員工掉盅，其他查詢員工的年齡都要和自己的管理者進行比較（選擇最小的）也拜，所以我在第一次搜索的時候就初始化result為無窮大，其他時候就把result初始化為這次搜索的員工的年齡趾痘。其次在多次搜索的時候會有重復的慢哈，增大了時間復雜度，所以我用一個二維數(shù)組來存儲搜索結果永票，如果已經(jīng)搜索過了卵贱，就直接返回二維數(shù)組中存儲的值，不必再進行重復的搜索（這里要注意一旦交換兩個員工的位置侣集，搜索結果就會發(fā)生改變键俱，所以在交換兩個員工位置之后就要將記憶數(shù)組給清空）。

代碼

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAX_N 500+10
using namespace std;

vector<int>G[MAX_N];
int number[MAX_N];
int dp[MAX_N][MAX_N];

int dfs(int num,int cnt)
{
    if(dp[num][cnt]>=1)
    {
        return dp[num][cnt];
    }
    int result;
    if(cnt==0)
        result=INF;
    else
        result=number[num];
    if(G[num].size()==0)
    {
         result=number[num];
         dp[num][cnt]=result;
         return result;
    }
    else
    {
        for(int i=0;i<G[num].size();i++)
        {
           result=min(dfs(G[num][i],1),result);
        }
    }
    return dp[num][cnt]=result;
}
int main(int argc, char const *argv[])
{
    int N,M,I;
    scanf("%d%d%d",&N,&M,&I);
    for(int i=1;i<=N;i++)
        scanf("%d",&number[i]);
    int a,b;
    for(int i=0;i<M;i++)
    {
        scanf("%d%d",&a,&b);
        G[b].push_back(a);
    }
    while(I--)
    {
        char d;
        getchar();
        scanf("%c",&d);
        if(d=='P')
        {
            int num;
            scanf("%d",&num);
            if(G[num].size()==0)
            {
                printf("*\n");
                continue;
            }
            else
            {
                int result1=dfs(num,0);
                printf("%d\n",result1);
                continue;
            }
        }
        else if(d=='T')
        {
            int temp;
            memset(dp,0,sizeof(dp));//一旦交換員工的位置世分，dp的結果就會發(fā)生改變
            vector<int>mid;
            mid.clear();//每一次交換矩陣兩行的時候長度都不一樣编振，所以要清空。
            int num1,num2;
            scanf("%d%d",&num1,&num2);
            for(int i=0;i<G[num1].size();i++)
            {
                mid.push_back(G[num1][i]);
            }   
            G[num1].clear();
            for(int i=0;i<G[num2].size();i++)
            {
                G[num1].push_back(G[num2][i]);
            }         
            G[num2].clear();
            for(int i=0;i<mid.size();i++)
            {
                G[num2].push_back(mid[i]);
            }
            for(int i=1;i<=N;i++)
            {
                for(int j=0;j<G[i].size();j++)
                {
                    if(G[i][j]==num1)
                        G[i][j]=num2;
                    else if(G[i][j]==num2)
                        G[i][j]=num1;
                }
            }
        }
    }
    return 0;
}

總結

最開始的時候交換矩陣兩行的時候想偷懶臭埋，想用指針直接交換兩行的值踪央，結果運行程序會崩，所以最終還是先用一個數(shù)組存儲下矩陣的一行瓢阴，遍歷來交換矩陣的兩行（切記在競賽中最好不要用指針）畅蹂。其次在這道題中，鄰接表荣恐，無窮大INF液斜，dfs都得到了很大的用處。