[Time Gate]?
https://www.luogu.org/problemnew/show/P2941
【解题思路】
Tarjan缩点，再在所有强连通分量中找一条最小的边作为强连通分量的边，因为还要回来，所以Ans最后要乘二
【code】
1 #include<bits/stdc++.h> 2 using namespace std; 3 inline int read() 4 { 5 int x=0; 6 char c=getchar(); 7 bool flag=0; 8 while(c<‘0‘||c>‘9‘) {if(c==‘-‘)flag=1;c=getchar();} 9 while(c>=‘0‘&&c<=‘9‘){x=(x+(x<<2)<<1)+ c-‘0‘;c=getchar();} 10 return flag?-x:x; 11 } 12 const int N=5005; 13 int n,step,tcl,ans=1e9+7; 14 vector<int>G[N]; 15 vector<int>cg[N]; 16 int dfn[N],vis[N],col[N],low[N]; 17 stack<int>s; 18 int d[N][N]; 19 inline void tarjan(int now) 20 { 21 vis[now]=1; 22 s.push(now); 23 low[now]=dfn[now]=++step; 24 for(int i=0;i<G[now].size();++i) 25 { 26 int to=G[now][i]; 27 if(!dfn[to]) 28 { 29 tarjan(to); 30 low[now]=min(low[now],low[to]); 31 } 32 else if(vis[to]) low[now]=min(low[now],dfn[to]); 33 } 34 if(dfn[now]==low[now]) 35 { 36 col[now]=++tcl; 37 vis[now]=0; 38 while(1) 39 { 40 int x=s.top();s.pop(); 41 col[x]=tcl; 42 vis[x]=0; 43 if(now==x) break; 44 } 45 } 46 }//板子 47 int main() 48 { 49 n=read(); 50 for(int i=1;i<=n;++i) 51 { 52 int x=read(),y=read(); 53 G[x].push_back(y),G[y].push_back(x); 54 }//双向边 55 for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i); 56 memset(d,0x3f3f,sizeof(d));//初始化（我就是忘记然后挂了一次） 57 for(int i=1;i<=n;++i) 58 { 59 for(int j=1;j<=n;++j) 60 { 61 int x=read(); 62 if(i==j) continue; 63 d[col[i]][col[j]]=min(d[col[i]][col[j]],x); 64 } 65 } 66 for(int i=1;i<=tcl;++i) 67 { 68 int res=0; 69 for(int j=1;j<=tcl;++j) if(i!=j) res+=d[i][j]; 70 ans=min(ans,res); 71 }//暴力枚举答案 72 printf("%dn",ans*2); 73 }