C++11(clang++ 3.9) 解法, 执行用时: 19ms, 内存消耗: 936K, 提交时间: 2020-05-11 20:00:38

#include<cmath>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 1e4+5;
class Edge{
public:
	int to,nxt;
	Edge(int to=0,int nxt=0):to(to),nxt(nxt){}
};
Edge edge[maxn<<1];
int depth[maxn];
int head[maxn];
int deg[maxn];
int val[maxn];
int cnt;

void init(){
	memset(edge,0,sizeof(edge));
	memset(head,0,sizeof(head));
	memset(deg,0,sizeof(deg));
	memset(val,0,sizeof(val));
	cnt = 1;
}
void add(int u,int v){	++deg[u]; edge[cnt] = Edge(v,head[u]); head[u] = cnt++;}

int bfs(int now){
	memset(depth,0,sizeof(depth));
	queue<int> que;
	vector<pair<int,int> > vec;
	que.push(now);
	depth[now] = 0;
	while(!que.empty()){
		int u = que.front(); que.pop(); 
		for(int i=head[u] ; i; i = edge[i].nxt){
			int v = edge[i].to;
			if(!depth[u]){                        //depth[u]==0的所有扩展结点加入队列 
				depth[v] = depth[u] + 1;
				que.push(v);
			}
			if(depth[v] == 1 && depth[u] == 1){
				vec.push_back(make_pair(u,v));
			}
		}
	}
	int tot = vec.size();
	int ans = 0;
	for(int i=0;i<tot;i++){
		int x1 = vec[i].first, y1 = vec[i].second;
		for(int j=i+1;j<tot;j++){
			int x2 = vec[j].first, y2 = vec[j].second;
			int temp = val[x1] + val[y1] + val[now] + val[x2] + val[y2];
			if(x1==x2||x1==y2) temp -= val[x1];
			if(y1==x2||y1==y2) temp -= val[y1];
			ans = max(ans,temp);
		}
	}
	return ans;
}
int main(){
	init();
	int N, M; scanf("%d%d",&N,&M);
	for(int i=0;i<N;i++) scanf("%d",&val[i]);
	for(int i=1;i<=M;i++){
		int u, v; scanf("%d%d",&u,&v);
		add(u,v); add(v,u);
	}	
	int res = 0; 
	for(int i=0;i<N;i++){
		if(deg[i]>1){
			res = max(res, bfs(i));
		}
//		printf("res = %d\n",res);
	}
	printf("%d\n",res);
} 

C++14(g++5.4) 解法, 执行用时: 14ms, 内存消耗: 872K, 提交时间: 2020-05-10 15:11:21

#include<bits/stdc++.h>
using namespace std;
#define maxn 10010
int m,n,i,j,cnt,u,v,ans;
int head[maxn],du[maxn],w[maxn],h[maxn];
struct edge
{
	int to,nxt;
}e[2*maxn];
void addedge(int u,int v)
{
	e[++cnt].nxt=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
int bfs(int x)
{
	int i,j,u,v;
	queue<int>q;
	vector<pair<int,int> >tr;
	vector<int>vis;
	q.push(x);
	while(!q.empty())
	{
		u=q.front();q.pop();
		if(h[u]>1)
		break;
		for(i=head[u];i;i=e[i].nxt)
		{
			v=e[i].to;
			if(h[u]==1&&h[v]==1)
			{
				tr.push_back(make_pair(u,v));
			}
			else
			{
				q.push(v);
				h[v]=h[u]+1;
				vis.push_back(v);
			}
		}	
	}
	for(i=0;i<vis.size();i++)
	{
		h[vis[i]]=0;
	}
	int res=0;
	for(i=0;i<tr.size();i++)
	{
	//	printf("%d %d %d\n",x,tr[i].first,tr[i].second);
		for(j=i+1;j<tr.size();j++)
		{
			int a1,a2,b1,b2;
			a1=tr[i].first;a2=tr[i].second;
			b1=tr[j].first;b2=tr[j].second;
			int tmp=w[a1]+w[a2]+w[b1]+w[b2]+w[x];
			if(a1==b1||a1==b2)
				tmp-=w[a1];
			if(a2==b1||a2==b2)
				tmp-=w[a2];
			res=max(res,tmp);
		
		}
	}
//	
	return res;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&w[i]);
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		u++,v++;
		addedge(u,v);
		addedge(v,u);
		du[u]++,du[v]++;
	}
	for(i=1;i<=n;i++)
	{
		if(du[i]>=2)
		{
			ans=max(ans,bfs(i));
		}
	}
	printf("%d\n",ans);
	return 0;
}