【问题描述】
无向连通图G 有 n 个点，m 条边。点从1 ~ n编号，编号为i 的点权值为$W_i$ 。
每条边长度都为1。对于图G 上的三元组 (u,v,w) ，如果$(u,w,v)$是 $(u,v)$之间的一

条最短路（这里指 w和u,v之间均有直接连边），则它将产生$W_u \times W_v$的联合权值。
请问图G 上所有可产生联合权值的三元组中，联合权值最大的是多少？所有
联合权值之和是多少？

【数据范围】

$n,m \leq 30000$

【题解】

发现了各种$O(n^2)$的算法，听说卡得过，然而并卡不过。

发现，只有三元环会出现要减的情况，其他情况和联合权值一模一样。

那就搞呗~怎样判断三元环？枚举两个，判是否直接连通，set套pair维护即可。

后面的话就枚举三元环即可。

# include <stdio.h>
# include <algorithm>
# include <vector>
# include <map>
# include <iostream>
using namespace std;
int n,m,w[30010],t; 
int ans1=-1;
long long ans2=0;
vector <int> g[30010];
vector <int> f[30010];
map < pair<int,int> , bool> s;
inline bool cmp(int a,int b) {
	return w[a]>w[b];
}
int main() {
	freopen("link.in","r",stdin);
	freopen("link.out","w",stdout);
	scanf("%d%d%d",&n,&m,&t);
	for (int i=1,u,v;i<=m;++i) {
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
		s[make_pair(u,v)]=1;
		s[make_pair(v,u)]=1;
	}
	for (int i=1;i<=n;++i) scanf("%d",&w[i]);
	for (int i=1;i<=n;++i) {
		sort(g[i].begin(),g[i].end(),cmp);
		int sizes=g[i].size(),_size=sizes;
		for (int j=0;j<sizes;++j) {
			int k=j+1;
			for (;k<sizes;++k) 
				if (s[make_pair(g[i][j],g[i][k])]==0) break;
			if(k!=sizes) {
				sizes=k;
				ans1=max(ans1,w[g[i][j]]*w[g[i][k]]);
			}
		}
		long long _0=0;
		for (int j=0;j<_size;++j) {
			ans2+=_0*1LL*w[g[i][j]];
			_0+=1LL*w[g[i][j]];
		}
	}
	for (int i=1;i<=n;++i) {
		int sizes=g[i].size();
		for (int j=0;j<sizes;++j)
			if(g[g[i][j]].size()>g[i].size() || (g[g[i][j]].size()==g[i].size() && g[i][j]>i)) {
				f[i].push_back(g[i][j]);
			}
	}
	for (int i=1;i<=n;++i) {
		int sizes=f[i].size();
		for (int j=0;j<sizes;++j) {
			int x=f[i][j],xsizes=f[x].size();
			for (int k=0;k<xsizes;++k)
				if(s[make_pair(i,f[x][k])])
					ans2-=1LL*(w[i]*w[f[x][k]]+w[f[x][k]]*w[x]+w[x]*w[i]);
		}
	}
	if (t!=2) printf("%d\n",ans1); else printf("0\n");
	if (t!=1) cout<<ans2*2<<endl; else printf("0\n");
	return 0;
}