2022牛客五一集训派对day3-F：Rikka with Line Graph题解

57 阅读 0 评论 38 点赞

我是靠谱客的博主飘逸荷花，最近开发中收集的这篇文章主要介绍2022牛客五一集训派对day3-F：Rikka with Line Graph题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：https://ac.nowcoder.com/acm/contest/33551/F
来源：牛客网

时间限制：C/C++ 10秒，其他语言20秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld题目描述

Line Graph L(G) can be considered as an operator on an undirected graph G just like Complementary Graph and Dual Graph.

Rikka generalizes Line Graph to edge-weighted undirected graphs. For a graph G=〈V,E〉G=〈V,E〉, L(G) is still an edge-weighted undirected graph which is constructed in the following way:
1. L(G) has |E| vertices and the ith vertex corresponds to the ith edge in G.
2. There is an edge between i,j in L(G) if and only if edge i and j have at least one common vertices in G. And the edge weight is equal to the sum of the weights of edge i and j in G.

For example, in the following picture, the right graph is the line graph of the left one. Vertex 1,2,3,4 in L(G) correspond to edge (1,2),(1,4),(1,3),(3,4) in G. And if all edges in the left graph have weight 1, the edges in the right graph will have weight 2.

Now, Rikka has an edge-weighted undirected complete graph G with n vertices. And she constructs a graph G'=L(G). It is clear that G' is connected.

Let d(i,j) be the length of the shortest path between vertex i,j in G'(the length of each edge is equal to its weight), K be the number of vertices in G', Rikka wants you to calculate ∑i=1K∑j=i+1Kd(i,j)∑i=1K∑j=i+1Kd(i,j).

输入描述:

The first line contains a single number t(1 ≤ t ≤ 3), the number of the testcases.
For each testcase, the first line contains one single integer n(2 ≤ n ≤ 500).
Then n lines follow, each line contains n integers wi,j(0 ≤ wi,j ≤ 109), the weight of each edge in G. Since there are no self circles in G, the value of wi,i is meaningless.
The input guarantees that for all 1 ≤ i ≠ j ≤ n, wi,i=0 and wi,j = wj,i.

输出描述:

For each testcase, output a single line with a single number, the answer modulo 998244353.

示例1

输入

输出

0
6
56

题意

边权无向图以以下方式构建:
1. L(G)有|E|个顶点，第i个顶点对应G的第i条边
2. L(G)中i,j之间存在一条边，当且仅当边i和j在G中至少有一个公共点，且边权值等于边i和j在G中的权值之和

将线图推广到边权无向图。当两条边存在至少一个公共点，边权值等于两边的权值之和。例如上图中，右边的图形是左边的线形图。L(G)中的顶点1,2,3,4对应于G中的边(1,2)，(1,4)，(1,3)，(3,4)。如果左图中的所有边权值为1，则右图中的边权值为2

构造了一个连通图G'=L(G)，d(i,j)是G'中顶点i,j之间的最短路径的长度，K是G'中顶点的数量

计算：

题解

floyd:假设n个点，点与点间有m条边（无独立的点），我们要求每个点到到其他n-1个点的最短路径，首先就是用邻接矩阵进行存图，初始化INF，读边后赋值，然后枚举每个点，以每个点k作为中转，看看其他点A以k作为中转点去到下一个点B的距离是不是比原来不中转的的距离小，如果A-->k-->B小于原来A->B的距离，那么我们就要更新A-->B的距离变为松弛后的距离；这样对n-1个点都枚举作为中转点进行松弛后，就能得到每个点到其他点的最短距离了。

求出连通图任意两点之间的最短距离，即两点对应的边的权值（起止点的那两条边和其他所有边只连一次）+中间最短路径权值*2

举个????：(a,b)->(c,d)=d(a,b) + d(c, d) + 2*min( d[a][c], d[a][d], d[b][c], d[b][d] )

无向完全图：有n(n-1)/2条边，扣除自身则为n(n-1)/2-1条边

假设两点间最短距离L有一最近的点k,则所有与k相连的边到L的最近距离都是k到L的最近距离，则最近距离即d(k-L)*n',n'为大于k的点数。使用sort排序，第k短的会被用(n-k)次，则n'=n-k

#include<bits/stdc++.h>
using namespace std;
const int maxn=5010;
const int mod=998244353;
long long a[maxn][maxn],d [maxn][maxn];
long long b[maxn];
void floyd(int n)
{
int i,j,k;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
}
int main(int argc, const char * argv[]) {
long long n,m,i,j,k,count=0,ans=0;
cin>>m;
while(m--){
cin>>n;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
cin>>a[i][j];
d[i][j]=a[i][j];
if(i==j) d[i][j]=0;
}
}
floyd(n);
count=n*(n-1)/2-1;
ans=0;
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
ans=(ans+count*a[i][j]%mod)%mod;
}
}
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
for(k=1;k<=n;k++){
b[k]=min(d[i][k],d[j][k]);
}
sort(b+1,b+n+1);
for(k=1;k<=n;k++){
ans=(ans+(n-k)*b[k]%mod)%mod;
}
}
}
cout<<ans<<endl;
}
return 0;
}