B3852 题解

Lyrith_with_xQ · 2023-09-17 13:05:05 · 题解

首先，读题。

思路

读题后，我们可以知道，题目会给出 T 个图，每个图有 n 个点，m 条边，每个点有一个权值 w_i，需要按照权值从小到大的顺序输出每个图中每个顶点的出边。

本题难点在于对每个顶点的出边排序，我们可以用邻接表存图，存完后对每个顶点的出边排序，输出即可。

代码

#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int> > nds[500005];//使用vector+pair存图 
int t,n,m,w[500005],a,b; 

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) 
        {
            scanf("%d",&w[i]);
            nds[i].clear();//因为有多组数据，所以每次输入时要清空邻接表 
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a,&b);
            nds[a].push_back(make_pair(w[b],b));//因为pair的排序是按照第一个值排序的，所以把权值放在前面 
        }
        for(int i=1;i<=n;i++)
        {
            sort(nds[i].begin(),nds[i].end());//对每个节点的出边进行排序 
            for(int j=0;j<nds[i].size();j++)cout<<nds[i][j].second<<" ";
            cout<<"\n";
        }
    }
    return 0;//华丽结束 
}

性能分析

时间复杂度：O(T \sum^{n}_{i=1} m_i \log m_i)。

空间复杂度：O(n+m)。

每个测试点最大用时：397ms。

可以通过本题。