题目链接：https://qoj.ac/contest/1386/problem/7580

题目大意：

有 $n$ 个未知数字，有 $m$ 个商人，每个商人有 $c_i$ 个的线索，每个线索有个价格，同时线索内容为 $[l,r]$ 的数字的和，你可以向每个商人买线索，但是每个商人必须恰好买 $k_i$ 个线索，问最少需要多少钱才能知道所有未知数字。

做法

虽然赛时队长神力秒了，但是我来编一个比较自然的思考路线：前缀和。

设 $s$ 为前缀和数组，所以实际上就是要知道所有 $s_i-s_0$ 。

考虑每个线索实际上提供了 $s_r-s_{l-1}$ ，又 $(s_a-s_b)+(s_b-s_c)=(s_a-s_c)$ ，所以实际上就是 $r$ 与 $l-1$ 连边，最后问所有点是不是与 $0$ 联通，也就是 $n+1$ 个点的生成树。

问题等价于 $n+1$ 个点，然后有一些边，问符合要求的最小权连通图。

  1. 第一个拟阵 ，图拟阵的对偶拟阵。
  2. 第二个拟阵 ，每个商人去掉的线索数量不超过 $c_i-k_i$ 。

带权拟阵交。

时间复杂度：$O((n\sum c_i)^2)$ 。

记得特判图一开始是不是联通的，因为如果一开始就不联通，那么 $\emptyset\notin \mathcal{I}$ ，这与拟阵交一开始默认 $\emptyset \in \mathcal{I}$ 冲突。

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
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int inf=1e9;
const int N=1e2+5;
const int M=2e4+5;

int n,m,K,ans,ned;
int bel[N],cnt[N],lim[N];
PII e[N];int pri[N];
bool in[N];
namespace Union{
    int fa[N];
    int findfa(int x){return fa[x]==x?x:fa[x]=findfa(fa[x]);}
    void mer(int x,int y){
        x=findfa(x);y=findfa(y);
        if(x!=y)fa[x]=y;
    }
    bool pd(int mov,int add){
        for(int i=0;i<=n;i++)fa[i]=i;
        for(int i=1;i<=K;i++){
            if(i==mov)continue;
            if(i!=add && in[i])continue;
            mer(e[i].first,e[i].second);
        }
        for(int i=1;i<=n;i++){
            if(findfa(i)!=findfa(0))return 0;
        }
        return 1;
    }
}
using Union::pd;

struct node{
    int y,next;
}a[M];int len,las[N];
void ins(int x,int y){a[++len]={y,las[x]};las[x]=len;}
int val[N],typ[N];PII d[N];
void init(){
    len=0;
    memset(las+1,0,sizeof(int)*K);
    memset(typ+1,0,sizeof(int)*K);
}
queue<int> q;bool v[N];
int pre[N];
bool solve(){
    for(int i=1;i<=K;i++)d[i]={-inf,-inf};
    assert(q.empty());
    for(int i=1;i<=K;i++){
        if(typ[i]&1){
            d[i]={val[i],0};
            v[i]=1;
            pre[i]=0;
            q.push(i);
        }
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        v[x]=0;
        for(int k=las[x];k;k=a[k].next){
            int y=a[k].y;
            if(PII{d[x].first+val[y],d[x].second-1}>d[y]){
                d[y]=PII{d[x].first+val[y],d[x].second-1};
                pre[y]=x;
                if(!v[y]){
                    v[y]=1;
                    q.push(y);
                }
            }
        }
    }
    PII maxval={-inf,-inf};
    int endpoint=0;
    for(int i=1;i<=K;i++){
        if((typ[i]&2) && d[i]>maxval){
            maxval=d[i];
            endpoint=i;
        }
    }
    if(!endpoint)return 0;
    ans-=maxval.first;ned--;
    int now=endpoint;
    while(now){
        if(in[now])cnt[bel[now]]--;
        else cnt[bel[now]]++;
        in[now]^=1;
        now=pre[now];
    }
    return 1;
}
void build(){
    init();
    for(int i=1;i<=K;i++){

        if(!in[i])val[i]=pri[i];
        else val[i]=-pri[i];
        
        if(in[i]){
            for(int j=1;j<=K;j++){
                if(in[j])continue;
                if(pd(j,i))ins(i,j);
                if(cnt[bel[j]]<lim[bel[j]] || bel[i]==bel[j])ins(j,i);
            }
        }
        else{
            if(pd(i,-1))typ[i]|=1;
            if(cnt[bel[i]]<lim[bel[i]])typ[i]|=2;
        }
    }
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        ans=ned=K=0;
        memset(cnt,0,sizeof(cnt));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int x;scanf("%d%d",&x,&lim[i]);
            lim[i]=x-lim[i];
            ned+=lim[i];
            for(int j=1;j<=x;j++){
                ++K;bel[K]=i;in[K]=0;
                int l,r;scanf("%d%d%d",&l,&r,&pri[K]);
                l--;
                e[K]={l,r};
                ans+=pri[K];
            }
        }
        if(!pd(-1,-1)){
            printf("-1\n");
            continue;
        }
        do{
            build();
        }while(solve());
        if(ned)ans=-1;
        printf("%d\n",ans);
    }
    return 0;
}