<div class="solution-view">
    <div class="row">
        <div class="col-md-6">
            <p>提交时间：2023-12-05 22:39:52</p>
        </div>
        <div class="col-md-6">
            <p>运行 ID: <a href="/solution/detail?id=23951">23951</a></p>
        </div>
    </div>
    <div class="pre"><p>#include&lt;iostream&gt;
#include&lt;cstring&gt;
using namespace std;
#define int long long
const int inf=0x3f3f3f3f3f3f3f3f;
#define N 18
int n,m,g[N][N];
namespace sub1{
    int head[N],to[N*N],nex[N*N],wei[N*N];
    int sta;
    inline void insert(int u,int v,int w,int id){
        to[id]=v;
        nex[id]=head[u];
        head[u]=id;
        wei[id]=w;
    }
    int ans=inf;
    bool vis1[N],vis2[N];
    void dfs1(int nd){
        vis1[nd]=true;
        for(int i=head[nd];i;i=nex[i])if(!vis1[to[i]]&amp;&amp;to[i]&amp;&amp;!(((sta&gt;&gt;((i&gt;&gt;1)-1))^i)&amp;1)){
            dfs1(to[i]);
        }
    }
    void dfs2(int nd){
        vis2[nd]=true;
        for(int i=head[nd];i;i=nex[i])if(!vis2[to[i]]&amp;&amp;to[i]&amp;&amp;(((sta&gt;&gt;((i&gt;&gt;1)-1))^i)&amp;1)){
            dfs2(to[i]);
        }
    }
    inline void update(int s){
        int sum=0;
        for(int i=1;i&lt;=m;i++){
            if(s&amp;(1&lt;&lt;(i-1)))sum+=wei[i&lt;&lt;1|1];
            else sum+=wei[i&lt;&lt;1];
        }
        sta=s;
        memset(vis1,0,sizeof(vis1));
        memset(vis2,0,sizeof(vis2));
        dfs1(1);
        dfs2(1);
        for(int i=1;i&lt;=n;i++)if(!vis1[i]||!vis2[i])return;
        ans=min(ans,sum);
    }
    int main(){
        int now=0;
        for(int i=1;i&lt;=n;i++){
            for(int j=i+1;j&lt;=n;j++)if(g[i][j]&gt;=0){
                now++;
                insert(i,j,g[i][j],now&lt;&lt;1);
                insert(j,i,g[j][i],now&lt;&lt;1|1);
            }
        }
        for(int i=0;i&lt;(1&lt;&lt;m);i++)update(i);
        if(ans&lt;inf)cout&lt;&lt;ans;
        else cout&lt;&lt;-1;
        return 0;
    }
}
int sum;
void init(){
    cin&gt;&gt;n;
    for(int i=1;i&lt;=n;i++)for(int j=1;j&lt;=n;j++)cin&gt;&gt;g[i][j];
    for(int i=1;i&lt;=n;i++){
        for(int j=i+1;j&lt;=n;j++)if(g[i][j]&gt;=0)m++;
    }
}
int pop[N];
inline int pop_count(int x){
    int cnt=0;
    while(x)cnt++,x-=x&amp;-x;
    return cnt;
}
#undef N
#define N 11
// int S[N][1&lt;&lt;N],T[N][1&lt;&lt;N];
int F[N][N][1&lt;&lt;N],G[1&lt;&lt;N];
signed main(){
    // freopen(&quot;anatomy/ex_anatomy2.in&quot;,&quot;r&quot;,stdin);
    init();
    for(int i=0;i&lt;(1&lt;&lt;n);i++)pop[i]=pop_count(i);
    if(m&lt;=20){
        sub1::main();
        return 0;
    }
    for(int i=1;i&lt;=n;i++)for(int j=1;j&lt;=n;j++)if(g[i][j]&lt;0)g[i][j]=-inf;
    for(int i=1;i&lt;=n;i++){
        for(int j=1;j&lt;i;j++){
            if(g[i][j]&gt;-inf){
                sum+=g[i][j];
                g[j][i]-=g[i][j];
                g[i][j]=0;
            }
        }
    }
    // for(int i=1;i&lt;=n;i++,cout&lt;&lt;&#039;\n&#039;)for(int j=1;j&lt;=n;j++)cout&lt;&lt;g[i][j]&lt;&lt;&#039; &#039;;
    memset(F,0x3f,sizeof(F));
    for(int i=1;i&lt;=n;i++)F[i][i][1&lt;&lt;(i-1)]=0;
    for(int i=0;i&lt;(1&lt;&lt;n);i++){
        for(int s=1;s&lt;=n;s++)if(i&amp;(1&lt;&lt;(s-1))){
            for(int t=1;t&lt;=n;t++)if(i&amp;(1&lt;&lt;(t-1))){
                if(s!=t||pop[i]==1){
                for(int j=1;j&lt;=n;j++)if(!(i&amp;(1&lt;&lt;(j-1)))){
                    if(g[t][j]&gt;-inf){
                        int nx=(i|(1&lt;&lt;(j-1)));
                        F[s][j][nx]=min(F[s][j][nx],F[s][t][i]+g[t][j]);
                    }
                }
                if(pop[i]&gt;2&amp;&amp;g[t][s]&gt;-inf)F[s][s][i]=min(F[s][s][i],F[s][t][i]+g[t][s]);
                }
            }
        }
    }
    memset(G,0x3f,sizeof(G));
    for(int i=1;i&lt;=n;i++)G[(1&lt;&lt;(i-1))]=0;
    for(int i=1;i&lt;(1&lt;&lt;n);i++){
        for(int sta=(((1&lt;&lt;n)-1)^i),j=sta;j;j=(j-1)&amp;sta){
            for(int s=1;s&lt;=n;s++)if(i&amp;(1&lt;&lt;(s-1))){
                for(int t=1;t&lt;=n;t++)if(i&amp;(1&lt;&lt;(t-1))){
                    G[i|j]=min(G[i|j],G[i]+F[s][t][j|(1&lt;&lt;(s-1))|(1&lt;&lt;(t-1))]);
                    
                }
            }
        }
    }
    if(G[(1&lt;&lt;n)-1]&lt;inf-(2e9))cout&lt;&lt;G[(1&lt;&lt;n)-1]+sum;
    else cout&lt;&lt;-1;
    // cerr&lt;&lt;((sizeof(F)+sizeof(S)+sizeof(T)+sizeof(G))&gt;&gt;20)&lt;&lt;endl;
    return 0;
}</p></div>
</div>
<script type="text/javascript">
    (function ($) {
        $(document).ready(function () {
            $('.pre p').each(function(i, block) {  // use <pre><p>
                hljs.highlightBlock(block);
            });
        })
    })(jQuery);
</script>