[圖論][最短路徑]OI練習題：P服務點設置

問題描述

爲了進一步普及九年義務教育，政府要在某鄉鎮建立P所希望小學，該鄉鎮共有n個村莊，村莊間的距離已知，請問學校建在哪P個村莊最好？（好壞的標準是學生就近入學，即在來上學的學生中，以最遠的學生走的路程爲標準。或者說最遠的學生與學校的距離儘可能的小。）

 

【輸入格式】

輸入由若干行組成，第一行有3個整數，n（1≤n≤100）、m（1≤m≤n*n）,p；n表示村莊數，m表示村莊間道路數。第2至m+1行是每條路的信息，每行三個整數，爲道路的起點、終點和兩村莊間距離。（村莊從0開始編號）

【輸出格式】

兩個整數，學校所在村莊編號(如果兩個以上村莊都適合建立學校，選擇編號小的兩個村莊建學校，輸出時按編號從小到大輸出)。

【輸入樣例】

輸入文件名：djsc.in

6 8 2

0 2 10

0 4 30

0 5 100

1 2 5

2 3 50

3 5 10

4 3 20

4 5 60

【輸出樣例】

輸出文件名：djsc.out

0 3

（感謝BYVoid大牛提供強力的正體中文轉換引擎OpenCC！）

【分析】

 這是個多源最短路問題，可以用Floyd算法找出任意兩點間的最短路，然後通過遞歸函數找出符合題目的P個點即可。

【滿分代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int Mat[101][101];
int N,M,P;
const int MAXN=1000000000;
int Min=MAXN;
int Village[101];
int TempVil[101];
int Temp=MAXN;

void init()
{
    scanf("%d %d %d",&N,&M,&P);
    for (int i=0;i<N;i++)
        for (int j=0;j<N;j++)
            Mat[i][j]=MAXN;
   
    int a,b,c;
    for (int i=0;i<M;i++)
    {
        cin>>a>>b>>c;
        Mat[a][b]=c;
        Mat[b][a]=c;
    }   
    return;
}

void Floyd()
{
    int temp;
    for (int k=0;k<N;k++)
    {
        for (int i=0;i<N;i++)
        {
            for (int j=0;j<N;j++)
            {
                temp=Mat[i][k]+Mat[k][j];
                if (Mat[i][j]>temp)
                {
                    Mat[i][j]=temp;
                }
            }
        }
    }
}

void check()
{
    bool isP[101]={false};
    for (int i=1;i<=P;i++)
    {
        isP[ TempVil[i] ]=true;
    }
   
    int TP;
    int MaxL=0;
    for (int i=0;i<N;i++)
    {
        if(isP[i])
            continue;
        int TMin=MAXN;
        for (int j=1;j<=P;j++)
        {
            TP=TempVil[j];
            if(Mat[i][TP]<TMin)
                TMin=Mat[i][TP];
        }
        if(TMin>MaxL)
            MaxL=TMin;
    }
   
    if(MaxL<Min)
    {
        Min=MaxL;
        for (int i=1;i<=P;i++)
            Village[i]=TempVil[i];
    }
}

void Works(int C,int Num)
{
    if(C==P+1)
    {
        bool flag=true;
        for (int i=1;i<=P-1;i++)
        {
            if (TempVil[i]>=TempVil[i+1])
            {
                flag=false;
                break;
            }
        }
        if(flag)
            check();
    }
    else
    {
        TempVil[C]=Num;
        for (int i=0;i<N;i++)
        {
            bool flag=true;
            for (int j=1;j<=C;j++)
            {
                if(TempVil[j]==i)
                {
                    flag=false;
                    break;
                }
            }
            if(flag)
                Works(C+1,i);
        }
    }
}

int main()
{
    freopen("djsc.in","r",stdin);
    freopen("djsc.out","w",stdout);
    init();
    Floyd();
    Works(0,0);
    for (int i=1;i<=P;i++)
        cout<<Village[i]<<" ";
   
    return 0;
}

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.000 s	312 KB	0
2	正确	10	0.000 s	312 KB	0
3	正确	10	0.000 s	312 KB	0
4	正确	10	0.075 s	312 KB	0
5	正确	10	0.066 s	312 KB	0
6	正确	10	0.738 s	312 KB	0
7	正确	10	0.131 s	312 KB	0
8	正确	10	0.498 s	312 KB	0
9	正确	10	0.019 s	312 KB	0
10	正确	10	0.753 s	312 KB	0

运行完成
运行时间 2.282 s
平均内存使用 312 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
已完成数据库校验。