Wuyanru's blog
0%

[QOJ9315] Rainbow Bracket Sequence

发表于 分类于 ，

额，为啥能想到模拟费用流想不到直接费用流。

题目链接。

题意

现在有 个位置，每一个位置有一个颜色 和一个权值 。

现在你需要将每一个位置放上左括号或者右括号，使得最后这个串变成一个合法括号串。

此外还有若干限制，对于每一个 需要有 个颜色为 的左括号。

一种方案的权值为，所有填了左括号的位置的权值和。求最大权值。

。

题解

考虑什么样的括号序列是合法的。

可以发现，只需要满足，对于每一个 满足前 个字符中有至少 个左括号，并且总共恰好有 个左括号就 ok。

那么考虑跑一个上下界最大费用流就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const ll L=1000000000000ll;
bool in[1001];
int head[1001];
int cur[1001];
int to[100001];
int nx[100001];
int w[100001];
ll c[100001];
ll dis[1001];
int l[1001];
int col[1001];
int v[1001];
int n,m,cntm,s,t;
inline void clear()
{
    cntm=1;
    memset(head,0,sizeof(head));
}
inline void ad(int u,int v,int ww,ll cc)
{
    cntm++;
    to[cntm]=v,w[cntm]=ww,c[cntm]=cc;
    nx[cntm]=head[u],head[u]=cntm;
}
inline void add(int u,int v,int w,ll c)
{
    // printf("%d %d (%d,%lld)\n",u,v,w,c);
    ad(u,v,w,c),ad(v,u,0,-c);
}
ll ans;
inline bool spfa()
{
    memset(dis,-0x3f,sizeof(dis));
    dis[s]=0;queue<int>que;que.push(s),in[s]=1;
    while(!que.empty())
    {
        int u=que.front();que.pop();in[u]=0;
        for(int i=head[u];i;i=nx[i]) if(w[i])
        {
            int p=to[i];ll val=dis[u]+c[i];
            if(val>dis[p])
            {
                dis[p]=val;
                if(!in[p]) in[p]=1,que.push(p);
            }
        }
    }
    return dis[t]!=dis[0];
}
int dfs(int u,int flow)
{
    if(in[u]) return 0;
    if(u==t) return flow;
    in[u]=1;
    int rest=flow;
    for(int &i=cur[u];i;i=nx[i]) if(w[i])
    {
        int p=to[i];
        if(dis[p]!=dis[u]+c[i]) continue;
        int num=dfs(p,min(rest,w[i]));
        rest-=num,w[i]-=num,w[i^1]+=num,ans+=c[i]*num;
        if(!rest){ in[u]=0;return flow;}
    }
    in[u]=0;
    return flow-rest;
}
inline void MCMF()
{
    int flow=0;ans=0;
    while(spfa())
    {
        memcpy(cur,head,sizeof(head));
        flow+=dfs(s,0x3f3f3f3f);
    }
    assert(flow==n);
}
inline void solve()
{
    n=read(),m=read(),s=2*n+m+1,t=s+1;
    int sum=0;
    for(int i=1;i<=m;i++)
    {
        l[i]=read();sum+=l[i];
        add(s,i+2*n,l[i],L);
        add(s,i+2*n,n,0);
    }
    for(int i=1;i<=2*n;i++) col[i]=read();
    for(int i=1;i<=2*n;i++)
    {
        v[i]=read();
        add(col[i]+2*n,i,1,v[i]);
        if(i!=1) add(i-1,i,n,0);
        if(i&1) add(i,t,1,0);
    }
    MCMF();
    if(ans<sum*L) printf("-1\n");
    else printf("%lld\n",ans-sum*L);
}
int main()
{
    int T=read();
    while(T--) clear(),solve();
    return 0;
}