代码如下:
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
#define N 1005
#define reint register int
int n,num,visn,stan,dfn[N],lows[N],sta[N],fa[N],k,ans;
vector<int>g[N];
vector<int>h[N];
stack<int>s;//ghs:干好事
struct Edge{
int from;
int to;
int val;
}edge[N*N];
inline bool cmp(Edge a,Edge b)
{
return a.val<b.val;
}
int finds(int x)
{
if(x!=fa[x])fa[x]=finds(fa[x]);
return fa[x];
}
inline void unions(int x,int y)
{
x=finds(x),y=finds(y);
fa[x]=y;
}
void Tarjan(int u)
{
dfn[u]=lows[u]=++visn;
s.push(u);
for(reint i=0;i<g[u].size();++i)
{
int v=g[u][i];
if(!dfn[v])
{
Tarjan(v);
lows[u]=min(lows[u],lows[v]);
}
else if(!sta[v])
lows[u]=min(lows[u],dfn[v]);
}
if(dfn[u]==lows[u])
{
sta[u]=++stan;
while(s.top()!=u)
{
sta[s.top()]=stan;
s.pop();
}
s.pop();
}
}
inline void starts()
{
memset(dfn,0,sizeof(dfn));
memset(lows,0,sizeof(lows));
memset(sta,0,sizeof(sta));
for(reint i=1;i<=n;++i)fa[i]=i;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
starts();
for(reint i=1;i<=n;++i)
{
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
for(reint i=1;i<=n;++i)
if(!dfn[i])Tarjan(i);
for(signed i=1;i<=n;++i)
for(signed j=1;j<=n;++j)
{
int val;
cin>>val;
if(sta[i]==sta[j])continue;
edge[++num].from=sta[i];
edge[num].to=sta[j];
edge[num].val=val;
}
sort(edge+1,edge+1+num,cmp);
for(signed i=1;i<=num;++i)
{
int x=edge[i].from,y=edge[i].to;
if(finds(x)!=finds(y))
{
unions(x,y);
ans+=edge[i].val;
++k;
if(k==stan-1)break;
}
}
cout<<ans*2<<'\n';
return 0;
}
(悲