[USACO09FEB]环绕岛屿Surround the Islands_C

概述[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()

[Time Gate]

https://www.luogu.org/problemnew/show/P2941

【解题思路】

Tarjan缩点，再在所有强连通分量中找一条最小的边作为强连通分量的边，因为还要回来，所以Ans最后要乘二

【code】

 1 #include<bits/stdc++.h> 2 using @R_419_6889@space 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("%d\n",ans*2);73 }