列表

详情

NC17696. Rikka with Line Graph

描述

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 , 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 .

输入描述

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

输入: 

3
2
0 1
1 0
3
0 1 1
1 0 1
1 1 0
4
0 1 1 1
1 0 2 2
1 2 0 3
1 2 3 0

输出: 

0
6
56

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 8348ms, 内存消耗: 1388K, 提交时间: 2018-08-19 15:34:16 

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

const int maxn = 500 + 9;
const int mod=998244353;
int T, N;
int w[maxn][maxn];
int dis[maxn];
ll inv2=(mod+1)>>1;
int main() 
{
	scanf("%d",&T);
	while(T--) 
	{
		scanf("%d", &N);
		ll ans=0;
		ll tim=N*(N-1)/2-1;
		for(int i = 0; i < N; i++) 
		{
			for(int j = 0; j < N; j++) 
			{
				scanf("%d", &w[i][j]);
				ans+=w[i][j];
			}
		}
		ans=ans%mod*tim%mod*inv2%mod;
		for(int k = 0; k < N; k++) 
		{
			for(int i = 0; i < N; i++) 
			{
				for(int j = 0; j < N; j++) 
				{
					w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
				}
			}
		}
		ll res=0;
		for(int i=0;i<N;++i) 
		{
			ll ret=0;
			for(int j=i+1;j<N;++j)
			{
				for(int k=0;k<N;++k) dis[k]=-min(w[i][k],w[j][k]);
				sort(dis,dis+N);
				for(int k=0;k<N;++k)
					ret+=(ll)(-dis[k])*(ll)k;
			}
			res=(res+ret)%mod;
		}
		ans+=res;
		if (ans>=mod) ans-=mod;
		printf("%lld\n",ans);
		
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 9586ms, 内存消耗: 2660K, 提交时间: 2020-03-29 15:13:57 

#include<bits/stdc++.h>
using namespace std;
#define go(i,a,b) for(int i=a;i<=b;i++)
#define mod 998244353
#define ll long long
#define N 555
ll w[N][N],m,n,t,ans,a[N];
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);m=n*(n-1)/2-1;ans=0;
        go(i,1,n)go(j,1,n)scanf("%lld",&w[i][j]);
        go(i,1,n)go(j,i+1,n)(ans+=w[i][j]*m%mod)%=mod;
        go(k,1,n)go(i,1,n)go(j,1,n)w[i][j]=min(w[i][j],w[i][k]+w[k][j]);
        go(i,1,n)go(j,i+1,n)
        {
            go(k,1,n)a[k]=min(w[i][k],w[j][k]);sort(a+1,a+1+n);
            go(k,1,n)(ans+=1ll*(n-k)*a[k]%mod)%=mod;
        }
        ans=(ans+mod)%mod;printf("%lld\n",ans);
    }
    return 0;
}

上一题

© 2024 nowcoder.com