题解 P2941 【[USACO09FEB]环绕岛屿Surround the Islands】

题目大意：给定n个点，求一条遍历所有点的最短路径 已知题目中所说的不同岛屿，易得为不同联通块，即 将每个岛屿缩成一个点 然后求一个最小生成树（其实没有必要写） 其实就是一个缩点的板子题吧。。。 本题说一条路径要走来回两次，所以最后答案需要$*2$ code ``` #include<bits/stdc++.h> using namespace std; inline int read() { int x=0; char c=getchar(); bool flag=0; while(c<'0'||c>'9') {if(c=='-')flag=1;c=getchar();} while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+ c-'0';c=getchar();} return flag?-x:x; } const int N=5005; int n,step,tcl,ans=1e9+7; vector<int>G[N]; vector<int>cg[N]; int dfn[N],vis[N],col[N],low[N]; stack<int>s; int d[N][N]; inline void tarjan(int now) { vis[now]=1; s.push(now); low[now]=dfn[now]=++step; for(int i=0;i<G[now].size();++i) { int to=G[now][i]; if(!dfn[to]) { tarjan(to); low[now]=min(low[now],low[to]); } else if(vis[to]) low[now]=min(low[now],dfn[to]); } if(dfn[now]==low[now]) { col[now]=++tcl; vis[now]=0; while(1) { int x=s.top();s.pop(); col[x]=tcl; vis[x]=0; if(now==x) break; } } }//板子 int main() { n=read(); for(int i=1;i<=n;++i) { int x=read(),y=read(); G[x].push_back(y),G[y].push_back(x); }//双向边 for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i); memset(d,0x3f3f,sizeof(d));//初始化（我就是忘记然后挂了一次） for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { int x=read(); if(i==j) continue; d[col[i]][col[j]]=min(d[col[i]][col[j]],x); } } for(int i=1;i<=tcl;++i) { int res=0; for(int j=1;j<=tcl;++j) if(i!=j) res+=d[i][j]; ans=min(ans,res); }//暴力枚举答案 printf("%d\n",ans*2); } ```