自动搬运

查看原文

来自洛谷，原作者为

	Lyrith_with_xQ 与你的日常，便是 ⌈ 奇迹 ⌋

搬运于2025-08-24 21:15:29，当前版本为作者最后更新于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$。

可以通过本题。