头像




在线 


最近来访(29)
用户头像
Miracle-
用户头像
7tai
用户头像
itdef
用户头像
冬天不能吃冰淇淋
用户头像
RyanMoriarty
用户头像
zouruiyang
用户头像
walkerㅤ
用户头像
autumn.
用户头像
mood_7
用户头像
Kurumi
用户头像
Peter_5
用户头像
算法小爱
用户头像
番红柿要吃西茄
用户头像
路过的老年人
用户头像
WanderOvO
用户头像
颜末
用户头像
かわいい子
用户头像
代码改变头发
用户头像
Fau
用户头像
Baily1234

活动打卡代码 AcWing 395. 冗余路径


12小时前
#include <bits/stdc++.h>
using namespace std;

const int N = 1010,M=40010;

int e[M],ne[M],h[N],idx;
int stk[N],top, dcc_cnt, d[N];
int n,m;
int dfn[N],low[N],timestamp;
bool is_bridge[N];
int id[N];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}


void tarjan(int u,int from)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;

    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j,i);
            low[u]=min(low[u],low[j]);
            if(dfn[u]<low[j]) is_bridge[i]=is_bridge[i^1]=true;
        }
        else if(i!=(from^1)) low[u]=min(low[u],dfn[j]);
    }

    if(dfn[u]==low[u])
    {
        ++dcc_cnt;
        int y;
        do{
            y=stk[top--];
            id[y]=dcc_cnt;
        }while(y!=u);
    }
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b; scanf("%d%d",&a,&b);
        add(a, b); add(b,a);
    }

    tarjan(1,-1);

    for(int i=0;i<idx;i++)
        if(is_bridge[i]) d[id[e[i]]]++;

    int res=0;
    for(int i=1;i<=n;i++)
        if(d[i]==1) res++;

    cout<<(res+1)/2<<endl;

    return 0;
}


活动打卡代码 AcWing 368. 银河


15小时前

直接拿糖果这题的代码也能过,本质一样的题,但是方法可以不一样,糖果的spfa不稳定,tarjan可以稳定$O(n+m)$

#include <bits/stdc++.h>
using namespace std;

const int N = 100010,M=600010; //add有可能双向边 3*N*3=6*N
typedef long long LL;

int n,m;
int dfn[N],low[N],Size[N],scc_cnt,timestamp;
int stk[N],top,id[N]; 
bool in_stk[N];
int dist[N];
int h[N],hs[N],e[M],ne[M],w[M],idx;

void add(int h[],int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    }

    if(low[u]==dfn[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
            Size[scc_cnt]++;
        }while(y!=u);
    }
}

int main()
{
    memset(h,-1,sizeof h);
    memset(hs,-1,sizeof hs);
    cin>>n>>m;

    for(int i=1;i<=n;i++) add(h,0,i,1);    

    for(int i=0;i<m;i++)
    {
        int t,a,b; scanf("%d%d%d",&t,&a,&b);
        if(t==1) add(h,a,b,0), add(h,b,a,0);
        else if(t==2) add(h,a,b,1);
        else if(t==3) add(h,b,a,0);
        else if(t==4) add(h,b,a,1);
        else add(h,a,b,0);
    }

    tarjan(0);

    bool flag=true;
    for(int i=0;i<=n;i++)
    {
        for(int j=h[i];~j;j=ne[j])
        {
            int a=id[i],b=id[e[j]];
            if(a==b)
            {
                if(w[j]>0) 
                {
                    flag=false;
                    break;
                }
            }
            else add(hs,a,b,w[j]);
        }
        if(!flag) break;
    }

    if(!flag) puts("-1");
    else 
    {
        for(int i=scc_cnt;i;i--)
        {
            for(int j=hs[i];~j;j=ne[j])
            {
                int k=e[j];
                dist[k]=max(dist[k],dist[i]+w[j]);
            }
        }

        LL res=0;
        for(int i=1;i<=scc_cnt;i++) res+=(LL)Size[i]*dist[i];

        cout<<res<<endl;
    }

    return 0;
}




17小时前
#include <bits/stdc++.h>
using namespace std;

const int N = 100010,M=2000010;
typedef long long LL;


int n,m,mod;
int stk[N],scc_cnt, top;
bool in_stk[N];
int e[M],ne[M],h[N],hs[N],idx;
int id[N], Size[N];
int dfn[N], low[N], timestamp;
int din[N], dout[N];
int g[N],f[N];
unordered_set<LL> S;

void add(int h[], int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j])
            low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt]++;
        } while (y != u);
    }
}


int main()
{
    memset(h, -1, sizeof h);
    memset(hs,-1,sizeof hs);
    cin>>n>>m>>mod;
    while (m -- ){
        int a,b; scanf("%d%d",&a,&b);
        add(h,a,b);
    }

    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);

    for(int i=1;i<=n;i++)
        for(int j=h[i];~j;j=ne[j])
        {
            int a=id[i], b=id[e[j]];
            int hash=a*1000000ll+b;
            if(a!=b&&!S.count(hash))  
            {
                add(hs,a,b);
                S.insert(hash);
            }
        }

    //f[i]:以 i 结尾的最大半连通子图的点数,和以 i 结尾的最大半连通子图的方案数
    for(int i=scc_cnt;i;i--)
    {
        if(!f[i]) 
        {
            f[i]=Size[i];
            g[i]=1;
        }
        for(int j=hs[i];~j;j=ne[j])
        {
            int k=e[j];
            if(f[k]<f[i]+Size[k])
            {
                f[k]=f[i]+Size[k];
                g[k]=g[i];
            }
            else if(f[k]==f[i]+Size[k])
                g[k]=(g[k]+g[i])%mod;
        }
    }

    int maxf=0,sum=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(f[i]>maxf) 
        {
            maxf=f[i];
            sum=g[i];
        }
        else if(f[i]==maxf) sum=(sum+g[i])%mod;
    }

    cout<<maxf<<endl;
    cout<<sum<<endl;

    return 0;
}


活动打卡代码 AcWing 367. 学校网络


18小时前

第一问:需要哪几个点操作可以覆盖图中的每一个点 答案:入读为0的强连通点
第二问:需要连几条边变为强连通图 答案:scc_cnt==1?0:max(cnt_in,cnt_out);
证明见视频

#include <bits/stdc++.h>
using namespace std;

const int N = 110,M=N*N;

int n;
int stk[N],scc_cnt, top;
bool in_stk[N];
int e[M],ne[M],h[N],idx;
int id[N]; //Size[N];
int dfn[N], low[N], timestamp;
int din[N], dout[N];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j])
            low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            //Size[scc_cnt]++;
        } while (y != u);
    }
}



int main()
{
    memset(h, -1, sizeof h);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x; 
        while(scanf("%d",&x),x) add(i,x);
    }

    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);

    for(int i=1;i<=n;i++)
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            if(id[k]!=id[i]) 
                din[id[k]]++, dout[id[i]]++;
        }

    int res1=0,res2=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(!din[i]) res1++;
        if(!dout[i]) res2++;
    }
    cout<<res1<<endl;
    if(scc_cnt==1) puts("0");
    else cout<<max(res1,res2)<<endl;

    return 0;
}


活动打卡代码 AcWing 1174. 受欢迎的牛


19小时前
#include <bits/stdc++.h>
using namespace std;

const int N = 10010,M=50010;

int n,m;
int e[M],ne[M],h[N],idx;
int dfn[N],low[N],timestamp;
int scc_cnt,id[N],Size[N];
int dout[N];
int stk[N],top;
bool in_stk[N];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u, in_stk[u]=true;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j]) low[u]=min(low[u],dfn[j]);
    }

    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do{
            y=stk[top--];
            in_stk[y]=false;
            id[y]=scc_cnt;
            Size[scc_cnt]++;
        }while(y!=u);
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin>>n>>m;
    while (m -- )
    {
        int a,b; scanf("%d%d",&a,&b);
        add(a, b);
    }

    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);

    for(int i=1;i<=n;i++)
    {
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            if(id[i]!=id[k])
            {
                add(i,k);
                dout[id[i]]++;
            }
        }
    }

    //求下每个强连通分量,如果出度为0,则可以统计
    //可以把强连通分量视为一个点,但里面可能不止一个点
    int zeros=0,sum=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(dout[i]==0)
        {
            zeros++;
            sum+=Size[i];
            if(zeros>1)
            {
                sum=0;
                break;
            }
        }
    }

    cout<<sum<<endl;

    return 0;
}


活动打卡代码 AcWing 352. 闇の連鎖


1天前
#include <bits/stdc++.h>
using namespace std;

const int N = 100010,M=200010;

int e[M],h[N],ne[M],idx;
int n,m,ans;
int depth[N], fa[N][18];
int cnt[N];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs()
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[1]=1;
    queue<int> q;
    q.push(1);
    while(q.size())
    {
        int t=q.front(); q.pop();

        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q.push(j);
                fa[j][0]=t;
                for(int k=1;k<=16;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];
            }
        }
    }
}

int lca(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=16;k>=0;k--)
    {
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    }
    if(a==b) return a;//可能有重边,这个还是加上
    for(int k=16;k>=0;k--)
    {
        if(fa[a][k]!=fa[b][k]) 
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    }
    return fa[a][0];
}

int dfs(int u,int fa)
{
    int res=cnt[u];
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j!=fa)
        {
            int t=dfs(j,u);
            if(t==0) ans+=m;
            else if(t==1) ans++;
            res+=t;
        }
    }

    return res;
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int a,b; scanf("%d%d",&a,&b);
        add(a,b), add(b,a);
    }

    bfs();

    for(int i=1;i<=m;i++)
    {
        int a,b; scanf("%d%d",&a,&b);
        int anc=lca(a,b);
        cnt[a]++, cnt[b]++, cnt[anc]-=2;
    }

    dfs(1,-1);

    cout<<ans<<endl;

    return 0;
}


活动打卡代码 AcWing 356. 次小生成树


1天前

次小生成树$O(mlog n)$版,代码是真的够长的

#include <bits/stdc++.h>
using namespace std;

const int N = 100010,M=300010, INF=0x3f3f3f3f;
typedef long long LL;

struct Edge
{
    int a,b, w;
    bool used;
    bool operator < (const Edge & oo) const
    {
        return w<oo.w;
    }
}edge[M];

int e[M],ne[M],w[M],h[N],idx;
int n,m;
int d1[N][18],d2[N][18],fa[N][18];
int pre[N];
int depth[N];

void add(int a, int b, int c)  // 添加一条边a->b,边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int find(int x)  // 并查集
{
    if (pre[x] != x) pre[x] = find(pre[x]);
    return pre[x];
}


LL kruskal()
{
    LL res=0;
    memset(h,-1,sizeof h);
    sort(edge,edge+m);
    for(int i=1;i<=n;i++) pre[i]=i;
    for(int i=0;i<m;i++)
    {
        int a=edge[i].a, b=edge[i].b, w=edge[i].w;
        int pa=find(a), pb=find(b);
        if(pa!=pb)
        {
            pre[pa]=pb;
            res+=edge[i].w;
            edge[i].used=true;
            add(a,b,w), add(b,a,w);
        }
    }

    return res;
}

void bfs()
{
    memset(depth,0x3f,sizeof depth);
    memset(d1,-0x3f,sizeof d1);
    memset(d2,-0x3f,sizeof d2);
    depth[0]=0, depth[1]=1;
    queue<int> q;
    q.push(1);

    while(q.size())
    {
        int t=q.front(); q.pop();

        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q.push(j);
                fa[j][0]=t, d1[j][0]=w[i], d2[j][0]=-INF;
                for(int k=1;k<=16;k++)
                {
                    int anc=fa[j][k-1];
                    fa[j][k]=fa[anc][k-1];
                    int distance[4]={d1[j][k-1],d1[anc][k-1],d2[j][k-1],d2[anc][k-1]};
                    for(int u=0;u<4;u++)
                    {
                        if(distance[u]>d1[j][k]) d2[j][k]=d1[j][k],d1[j][k]=distance[u];
                        else if(distance[u]!=d1[j][k]&&distance[u]>d2[j][k]) d2[j][k]=distance[u];
                    }
                }
            }
        }
    }
}

int lca(int a,int b,int w)
{
    static int d[N*2];
    int cnt=0;
    if(depth[a]<depth[b]) swap(a,b);

    for(int k=16;k>=0;k--)
    {
        if(depth[fa[a][k]]>=depth[b]) 
        {
            d[cnt++]=d1[a][k];
            d[cnt++]=d2[a][k];
            a=fa[a][k];
        }
    }

    if(a!=b)
    {
        for(int k=16;k>=0;k--)
        {
            if(fa[a][k]!=fa[b][k])
            {
                d[cnt++]=d1[a][k];
                d[cnt++]=d2[a][k];
                d[cnt++]=d1[b][k];
                d[cnt++]=d2[b][k];
                a=fa[a][k], b=fa[b][k];
            }
        }
        d[cnt++]=d1[a][0], d[cnt++]=d1[b][0];
    }


    int res1=-INF,res2=-INF;
    for(int i=0;i<cnt;i++)
    {
        if(d[i]>res1) res2=res1,res1=d[i];
        else if(d[i]!=res1&&d[i]>res2) res2=d[i];
    }

    if(w>res1) return w-res1;
    if(w>res2) return w-res2;
    return INF;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b, c; scanf("%d%d%d",&a,&b,&c);
        edge[i]={a,b,c};
    }

    LL sum=kruskal();

    bfs();

    LL res=1e18;
    for(int i=0;i<m;i++)
    {
        if(!edge[i].used)
        {
            int a=edge[i].a, b=edge[i].b, w=edge[i].w;
            res=min(res,sum+lca(a,b,w));
        }
    }

    cout<<res<<endl;

    return 0;
}


活动打卡代码 AcWing 1171. 距离


1天前

tarjan 做法

#include <bits/stdc++.h>
using namespace std;

const int N = 40010,M=80010;
typedef pair<int, int> PII;

int n,m,res[N];
int e[M],ne[M],h[N],w[M],idx;
int dist[N];
int pre[N], st[N];
vector<PII> Query[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int find(int x)
{
    return x==pre[x]?x:pre[x]=find(pre[x]);
}

void dfs(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j!=fa)
        {
            dist[j]=dist[u]+w[i];
            dfs(j,u);
        }
    }
}

void tarjan(int u)
{
    st[u]=1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            tarjan(j);
            pre[j]=u;
        }
    }

    for(auto x:Query[u])
    {
        int y=x.first, id=x.second;
        int anc=find(y);
        if(st[y]==2)
            res[id]=dist[y]+dist[u]-2*dist[anc];
    }

    st[u]=2;
}


int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
        add(a,b,c), add(b,a,c);
    }

    for(int i=1;i<=m;i++)
    {
        int a,b; scanf("%d%d",&a,&b);
        if(a!=b)
        {
            Query[a].push_back({b,i});
            Query[b].push_back({a,i});
        }

    }

    for(int i=1;i<=n;i++) pre[i]=i;

    dfs(1,-1);

    tarjan(1);

    for(int i=1;i<=m;i++) printf("%d\n",res[i]);

    return 0;
}`

倍增做法

#include <bits/stdc++.h>
using namespace std;

const int N = 40010,M=80010;

int n,m;
int depth[N],fa[N][17];
int e[M],ne[M],h[N],w[M],idx;
int dist[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[root]=1;

    queue<int> q;
    q.push(root);
    while(q.size())
    {
        int u=q.front(); q.pop();

        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[u]+1)
            {
                depth[j]=depth[u]+1;
                dist[j]=dist[u]+w[i];
                q.push(j);
                fa[j][0]=u;
                for(int k=1;k<=16;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];
            }
        }
    }
}

int lca(int a,int b)
{
    int res=0;
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=16;k>=0;k--)
        if(depth[fa[a][k]]>=depth[b])
        {
            res+=dist[a]-dist[fa[a][k]];
            a=fa[a][k];
        }
    if(a==b) return res;
    for(int k=16;k>=0;k--)
        if(fa[a][k]!=fa[b][k])
        {
            res+=dist[a]-dist[fa[a][k]]+dist[b]-dist[fa[b][k]];
            a=fa[a][k], b=fa[b][k];
        }
    res+=dist[a]-dist[fa[a][0]]+dist[b]-dist[fa[b][0]];
    return res;
}


int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
        add(a,b,c), add(b,a,c);
    }

    bfs(1);

    while (m -- )
    {
        int a,b; scanf("%d%d",&a,&b);
        int t=lca(a,b);
        printf("%d\n",t);
    }

    return 0;
}


活动打卡代码 AcWing 1172. 祖孙询问


1天前
#include <bits/stdc++.h>
using namespace std;

const int N = 40010,M=80010;

int n,m;
int depth[N],fa[N][17];
int e[M],ne[M],h[N],idx;


void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}


void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0, depth[root]=1;

    queue<int> q;
    q.push(root);
    while(q.size())
    {
        int u=q.front(); q.pop();
        for(int i=h[u];~i;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[u]+1)
            {
                depth[j]=depth[u]+1;
                fa[j][0]=u;
                for(int k=1;k<=16;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];

                q.push(j);
            }
        }
    }
}

int lca(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);

    for(int k=16;k>=0;k--)
    {
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    }

    if(a==b) return a;

    for(int k=16;k>=0;k--)
    {
        if(fa[a][k]!=fa[b][k]) 
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    }
    return fa[a][0];
}


int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    int root;
    for(int i=0;i<n;i++)
    {
        int a,b; scanf("%d%d",&a,&b);

        if(b==-1) root=a;
        else add(a,b), add(b,a);
    }

    bfs(root);

    cin>>m;
    while (m -- )
    {
        int a,b; scanf("%d%d",&a,&b);
        int f=lca(a,b);
        if(a==f) puts("1");
        else if(b==f) puts("2");
        else puts("0");
    }

    return 0;
}


活动打卡代码 AcWing 393. 雇佣收银员


2天前
#include <bits/stdc++.h>
using namespace std;

const int N = 1010,M=110;
const int INF=0x3f3f3f3f;

int e[M],h[M],ne[M],w[M],idx;
int n, r[M], num[M];
int dist[M],cnt[M];
bool st[M];

void add(int a, int b, int c)  // 添加一条边a->b,边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa()
{
    memset(cnt,0,sizeof cnt);
    memset(dist,-0x3f,sizeof dist);
    memset(st,0,sizeof st);
    dist[0]=0;

    queue<int> q;
    q.push(0);

    while(q.size())
    {
        int t=q.front(); q.pop();

        st[t]=false;

        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]<dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=25) return false;
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }

    return true;
}

int main()
{
    int T; cin>>T;
    while(T--)
    {
        for(int i=1;i<=24;i++) cin>>r[i];

        memset(num,0,sizeof num);
        cin>>n;
        for(int i=0;i<n;i++)
        {
            int x; scanf("%d",&x);
            num[x+1]++;
        }

        int res=0;
        for(int k=0;k<=1000;k++)
        {
            memset(h,-1,sizeof h);
            idx=0;
            add(0,24,k), add(24,0,-k);
            for(int i=1;i<=24;i++)
            {
                add(i-1,i,0);
                add(i,i-1,-num[i]);
                if(i>=8) add(i-8,i,r[i]);
                else add(i+16,i,r[i]-k);
            }

            if(spfa())
            {
                res=k;
                break;
            }
        }

        if(res) printf("%d\n",res);
        else puts("No Solution");
    }

    return 0;
}