省队集训-0424模拟赛
allenchoi
·
·
个人记录
A.图上的游戏
题意：
有一张图，n 个点，每个点有颜色 \in\set{0,1,2}，随机产生 m 条有向边（可重可自环）。然后 A,B 两个人博弈，轮流操作，一次可以将一个颜色为 2 的点染成 1 或 2，直到不存在颜色为 2 的点。最终分数为：所有两端颜色不同的边中，0\rightarrow1 的边的个数，减去 1\rightarrow0 的边的个数。A 想要最大化得分，B 想要最小化得分。
给定 N,M，以及 N 个点的颜色。\forall i \le N,j\le M，求当只保留 [1,i] 的点（即 n=i），且 m=j 时，对于所有的 n^{2m} 种情况，博弈分数的总和为多少。
#### Sol：
设 $v_i$ 表示一个点的出度减入度，则分数为 $\frac{1}{2}(\sum\limits_{c_i=0}v_i-\sum\limits_{c_i=1}v_i)$。图定下来后 $v_i$ 就确定了，于是两人会按照 $|v_i|$ 降序把所有 $c_i=2$ 的点排序，然后贪心选择。
考虑如何计算分数总和。
首先，$c_i\ne2$ 的点本身不影响总和，只影响方案数，因为把所有边都反转它就要做负贡献，抵消掉。
然后我们可以按 $|v_i|$ 降序，枚举所有的点可能的出度入度个数的对，总共有 $O(n^2)$ 种，然后做一个背包（因为总出度、入读都是 $m$），维护方案数和总和。
我们可以把 $m$ 条有向边，看成两个独立的长为 $m$ 的出点、入点序列，于是贡献系数就可以 $O(1)$ 计算：
设出度入度分别为 $a,b$，已经用了 $i$ 个 $col=2$ 的点，$j$ 的入度，$k$ 的出度，维护方案数、总和。枚举 $(a,b)$ 个数 $c$，有 $ca,cb\le m$，乘上 $\frac{1}{k!(a!b!)^c}$ 的系数，转移到 $(i+c,j+ac,k+bc)$，总和加上 $(c\mod 2)|a-b|$。
然后是统计答案：
注意我们只对 $col=2$ 的点做了背包。设 $e$ 为 $col=2$ 的点的个数。首先要乘上 $e!m!m!$（划分多组的组合数系数）。考虑剩下的点的出、入度，先乘上 $\frac{1}{(m-j)!(m-k)!}$，表示把剩下的点当成特殊的一组，然后乘上 $(n-e)^{m-j+m-k}$ 的方案数。
由于转移时有 $ca,cb\le m$，所以总复杂度 $O(\frac{n^6}{\log^2})$。
#### Code：
~~~cpp
#include <bits/stdc++.h>
#define pii pair <int,int>
#define fi first
#define se second
#define mkp make_pair
using namespace std;
const int N = 55,mod = 1e9 + 7;
int n,m,cnt,f[N][N][N],g[N][N][N],inv[N],fac[N],ifac[N],mi[N << 1],col[N];
pii p[N * N];
bool cmp(pii x,pii y){return abs(x.fi - x.se) > abs(y.fi - y.se);}
int main()
{
inv[1] = fac[0] = ifac[0] = 1;
for(int i = 2;i < N;i++) inv[i] = mod - 1LL * (mod / i) * inv[mod % i] % mod;
for(int i = 1;i < N;i++) fac[i] = 1LL * fac[i - 1] * i % mod;
for(int i = 1;i < N;i++) ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i = 0;i <= m;i++)
for(int j = 0;j <= m;j++)
p[++cnt] = mkp(i,j);
sort(p + 1,p + cnt + 1,cmp);
f[0][0][0] = 1;
for(int i = 1;i <= cnt;i++)
{
int a = p[i].fi,b = p[i].se,c = abs(a - b);
for(int j = n;j >= 0;j--)
for(int k = 1,s = 1;k <= j && k * a <= m && k * b <= m;k++)
{
s = 1LL * s * inv[k] % mod * ifac[a] % mod * ifac[b] % mod;
for(int x = k * a;x <= m;x++)
for(int y = k * b;y <= m;y++)
{
int v = 1LL * f[j - k][x - k * a][y - k * b] * s % mod;
f[j][x][y] = (f[j][x][y] + v) % mod;
g[j][x][y] = (g[j][x][y] + 1LL * g[j - k][x - k * a][y - k * b] * s % mod) % mod;
if(k & 1)
if(j & 1) g[j][x][y] = (g[j][x][y] + 1LL * v * c % mod) % mod;
else g[j][x][y] = (g[j][x][y] - 1LL * v * c % mod + mod) % mod;
}
}
}
for(int i = 1;i <= n;i++) scanf("%d",&col[i]);
for(int i = 1,e = 0;i <= n;i++)
{
e += (col[i] == 2),mi[0] = 1;
for(int j = 1;j <= 2 * m;j++) mi[j] = 1LL * mi[j - 1] * (i - e) % mod;
for(int j = 1;j <= m;j++)
{
int ans = 0;
for(int x = 0;x <= j;x++)
for(int y = 0;y <= j;y++)
ans = (ans + 1LL * g[e][x][y] * fac[e] % mod * fac[j] % mod * fac[j] % mod * mi[j - x + j - y] % mod * ifac[j - x] % mod * ifac[j - y] % mod) % mod;
ans = 1LL * ans * (mod / 2 + 1) % mod;
printf("%d ",ans);
}
puts("");
}
return 0;
}
~~~
### B.修理：
#### 题意：
有一个序列 $a$，和一个初始为 $0$ 的变量 $x$，可以进行一下两种操作：
>1.$x\leftarrow x+1
2.a_i\leftarrow a_i\oplus x
定义这个序列的代价，为最小的操作次数使得 a_i 全零。
给定一个长为 n 的序列，每次询问一个子区间 [l,r] 的代价，强制在线。
Sol：
设 $H$ 为 $\max highbit(a_i)$，则 $\le H$ 的 $a_i$ 贡献一定为 $1$，**可以只考虑 $>H$ 的点**。
扫描 $r$，对每个 $l$ 维护答案，用可持久化数据结构存答案，然后在线回答。考虑 $r+1$ 时对答案的影响。
贡献其实可以写成 $2len+x-\sum[a_i\le x](x\ge H)$，设 $d(x)=x-H-\sum[a_i\le x]$，则要最小化 $d(x)$，答案为 $2len+H+\min d(x)$。
设最优 $x$ 为使得 $d(x)$ 最小时最小的 $x$。不难发现随着区间扩展，$\min d(x)$ 不增而且最多减少 $1$，因为后面一个求和式最多加一，而且取得最优的 $x$ 不降。
同时，我们一定可以找出一个分界点 $m$，使得 $l\le m$ 的区间 $d_(x)-1$，$l>m$ 的区间 $d(x)$ 不变，证明如下：
设 $l_1<l_2$，且 $d_{l_2}$ 更新。设 $x_1=x_{[l_1,r]},x_2=x_{[l_2,r]},t=x_{[l_2,r+1]}$，显然有 $x_1\ge x_2,t\ge a_{r+1}$，因此 $d_{[l_2,r+1]}(t)=d_{[l_2,r]}(t)-1=d_{[l_2,r]}(x_2)-1$。
若 $a_{r+1}\le x_1$ 则 $\min d_{l_1}$ 一定更新；
考虑 $x_1<a_{r+1}$。注意到新加入一个数会让 $d(x)$ 的一个后缀减一，所以较小位置与较大位置的 $d(x)$ 之差只会扩大。
所以 $d_{[l_1,r]}(x_1)-d_{[l_1,r]}(t)\ge d_{[l_1,r]}(x_2)-d_{[l_1,r]}(t)\ge d_{[l_2,r]}(x_2)-d_{[l_2,r]}(t)=-1$，因此 $d_{l_1}$ 也会更新。
考虑求出 $m$。
可以证明 $a_m$ 在后续是没有影响的。首先有 $x_{[m,r+1]}\ge a_m$，否则 $d_{[m,r+1]}(x_{[m,r+1]})=d_{[m+1,r+1]}(x_{[m,r+1]})$，$m+1$ 也会更新。
又因为 $x$ 递增，所以 $L\le m,R\ge r+1$ 一定有 $x_{[L,R]}\ge x_{[m,r+1]}$，所以 $a_m$ 后面只有 $1$ 的贡献，可以打上**答案永久 $-1$ 的标记**然后把 $a_m$ 删掉。
设受删除影响后的 $d(x)$ 为 $d'(x)$。假设加入 $a_{r+1}$ 后，$d'_{[1,r+1]}(x)$ 最小的一个小于 $0$ 的位置为 $v$。
如果不存在这样的 $v$，则 $\min d(x)$ 不改变（$m=0$）；否则，$m$ 为 $\min\limits_{i 未删除 \land a_i\le v}i$。下面给出证明。
首先可以归纳证明，每次删掉 $a_m$ 后，$\forall x,d'(x)\ge 0$ 。
考虑加入 $a_{r+1}$ 后一个满足 $d'_{[l,r+1]}(t)<0$ 的位置，显然有 $t\ge a_{r+1}$。
如果 $x_{[l,r]}\ge a_{r+1}$，则答案一定会更新；
否则 $x<t$，把 $x$ 改成 $t$ 一定更优。因为 $d(x)=d'(x)+标记$，而由于 $x$ 递增，所以上文中标记只与区间端点有关。
对于 $d'_{[1,r+1]}(x)$ 中一个 $<0$ 的位置 $t$，设 $minn_t$ 表示 $\min\limits_{i 未删除 \land a_i\le t}i$，则显然 $\forall i\le minn_t,d'_{[i,r+1]}(t)=d'_{[1,r+1]}(t)<0$，因为 $d(x)$ 中后面的和式值不变。
显然 $minn_t$ 随 $t$ 增大而减小，而 $t\le v$，所以 $m=minn_v$。
考虑用一棵值域线段树维护 $[1,r]$ 中未被删除的值，以维护 $d'(x)$，$v$ 可以在上面线段树二分求得。再对每个 $H$ 开一个可持久化线段树存下标记即可。
时空复杂度 $O(n\log n)$。
代码里好像把 $d(x)$ 全部取负数了、、
#### Code：
~~~cpp
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int N = 2e5 + 5,INF = 2e9;
int n,Q,T,c[60],s[60],id[N],nxt[N],pos[N],rt[N][60],q[N][60];
ll a[N];
struct SgT1
{
#define ls (x << 1)
#define rs (ls | 1)
int minn[N << 2],maxn[N << 2],tag[N << 2];
void upd(int x,int v){maxn[x] += v,tag[x] += v;}
void pushdown(int x){if(tag[x]) upd(ls,tag[x]),upd(rs,tag[x]),tag[x] = 0;}
void pushup(int x){minn[x] = min(minn[ls],minn[rs]),maxn[x] = max(maxn[ls],maxn[rs]);}
void update1(int x,int l,int r,int p,int a,int b)
{
if(l == r) return (void)(minn[x] = a,maxn[x] += b);
pushdown(x);
if(p <= mid) update1(ls,l,mid,p,a,b);
else update1(rs,mid + 1,r,p,a,b);
pushup(x);
}
void update2(int x,int l,int r,int L,int R,int v)
{
if(L <= l && r <= R) return upd(x,v);
pushdown(x);
if(L <= mid) update2(ls,l,mid,L,R,v);
if(R > mid) update2(rs,mid + 1,r,L,R,v);
pushup(x);
}
int find(int x,int l,int r,int L,int R)
{
if(maxn[x] <= 0) return 0;
if(l == r) return l;
pushdown(x);
if(L <= l && r <= R)
{
if(maxn[ls] > 0) return find(ls,l,mid,L,R);
return find(rs,mid + 1,r,L,R);
}
int ret = 0;
if(L <= mid && (ret = find(ls,l,mid,L,R))) return ret;
if(R > mid) ret = find(rs,mid + 1,r,L,R);
return ret;
}
int query(int x,int l,int r,int L,int R)
{
if(L <= l && r <= R) return minn[x];
pushdown(x);
if(R <= mid) return query(ls,l,mid,L,R);
if(L > mid) return query(rs,mid + 1,r,L,R);
return min(query(ls,l,mid,L,R),query(rs,mid + 1,r,L,R));
}
#undef ls
#undef rs
} tr1;
struct SgT2
{
int tot,sum[N * 20],ls[N * 20],rs[N * 20];
int update(int o,int l,int r,int p)
{
int x = ++tot;
sum[x] = sum[o] + 1;
if(l == r) return x;
if(p <= mid) ls[x] = update(ls[o],l,mid,p),rs[x] = rs[o];
else rs[x] = update(rs[o],mid + 1,r,p),ls[x] = ls[o];
return x;
}
int query(int x,int l,int r,int L,int R)
{
if(!x) return 0;
if(L <= l && r <= R) return sum[x];
if(R <= mid) return query(ls[x],l,mid,L,R);
if(L > mid) return query(rs[x],mid + 1,r,L,R);
return query(ls[x],l,mid,L,R) + query(rs[x],mid + 1,r,L,R);
}
} tr2;
int main()
{
freopen("repair.in","r",stdin);
freopen("repair.out","w",stdout);
scanf("%d%d%d",&n,&Q,&T);
for(int i = 1;i <= n;i++) scanf("%lld",&a[i]);
for(int i = 1;i <= n;i++) c[__lg(a[i])]++;
for(int i = 0;i < 60;i++) s[i] = (i ? s[i - 1] : 0) + c[i];
for(int i = 0,id = 0;i < 60;i++) for(int j = 1;j <= c[i];j++) tr1.update1(1,1,n,++id,INF,1 - j);
fill(pos + 1,pos + n + 1,n + 1);
for(int i = n;i >= 1;i--)
{
int t = __lg(a[i]);
ll r = a[i] - (1LL << t);
if(r >= c[t]) continue;
id[i] = (t ? s[t - 1] : 0) + r + 1;
nxt[i] = pos[id[i]],pos[id[i]] = i;
}
memset(pos,0,sizeof(pos));
for(int i = 1;i <= n;i++)
{
memcpy(rt[i],rt[i - 1],sizeof(rt[i]));
memcpy(q[i],q[i - 1],sizeof(q[i]));
int t = __lg(a[i]);
ll r = a[i] - (1LL << t);
q[i][t]++;
if(r >= c[t]) continue;
if(!pos[id[i]]) tr1.update1(1,1,n,id[i],i,0),pos[id[i]] = i;
tr1.update2(1,1,n,id[i],s[t],1);
int v = tr1.find(1,1,n,id[i],s[t]);
if(v)
{
int p = tr1.query(1,1,n,(t ? s[t - 1] : 0) + 1,v);
rt[i][t] = tr2.update(rt[i][t],1,n,p);
if(nxt[p] <= i) tr1.update1(1,1,n,id[p],nxt[p],0),pos[id[p]] = nxt[p];
else tr1.update1(1,1,n,id[p],INF,0),pos[id[p]] = 0;
tr1.update2(1,1,n,id[p],s[t],-1);
}
}
ll lst = 0,l,r;
for(int i = 1,t;i <= Q;i++)
{
scanf("%lld%lld",&l,&r);
if(T == 2) l ^= lst,r ^= lst;
if(l > r) swap(l,r);
for(t = 59;q[r][t] - q[l - 1][t] == 0;t--);
lst = (1LL << t) + r - l + 1 + q[r][t] - q[l - 1][t] - tr2.query(rt[r][t],1,n,l,r);
printf("%lld\n",lst);
}
return 0;
}
~~~
### C.人员调度2
#### 题意：
要做二分图匹配，左右各 $n$ 个点，$i,j$ 匹配贡献为 $a_i+b_j+(a_i\oplus b_j)$。此外有 $m$ 个特殊边 $(i,j,v)$，表示 $i,j$ 匹配有额外 $v$ 的贡献。
给定 $K$，$\forall i\le K$，回答恰好匹配 $K$ 对时候的最大值。
$K\le 300,n\le 10^5,a_i,b_i<2^{12},v\le2\times10^5$。
#### Sol：
拆位看基础贡献，其实是 $2(a_i|b_j)$。直接跑 $K$ 轮增广路的话是 $O(Kn^3)$ 的。
##### 法一：
观察匈牙利算法的增广路，发现要么从左边直接到右边，要么中间经过一些匹配过的点。
值域比较小，直接每次 $O(V)$ 处理出和一个点最优的为匹配点，然后 $O(K^3)$ floyd 跑已匹配点的最短路。
$O(K^4+Kn+KV)$。
##### 法二：
首先每个点只用保留和自己连接的所有边中前 $K$ 大的；
其次，在上述保留的边中，只用取前 $O(K^2)$ 条。因为用一条边会尽调与之相连的边，最多 $O(K)$ 条。所以可以通过调整法把每一条边都变成前 $O(K^2)$ 大的。
~~由于数据范围和时限比较逆天两个都过不了，所以把两个做法绑一起，其中法二的 $O(K^2)$ 对 $10000$ 取 $\min$。~~
#### Code：
~~~cpp
#include <bits/stdc++.h>
#define pii pair <int,int>
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
#define il inline
using namespace std;
typedef long long ll;
il int read()
{
int x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
return x;
}
const int N = 1e5 + 5,M = 305,V = (1 << 12),INF = 2e9;
int n,m,K;
namespace AAA
{
int cnt,a[N],b[N],d1[N],d2[N],id1[N],id2[N],used[N],vis[N];
int cnt1[V],cnt2[V],cur1[V],cur2[V],s1[V][M],s2[V][M];
vector <int> t[V],w1[V],w2[V],p[N];
struct Edge{int x,y,z;};
vector <Edge> e,p1[N],p2[N];
bool cmp1(Edge x,Edge y){return x.z > y.z;}
bool cmp2(Edge x,Edge y){return x.x < y.x;}
struct Flow
{
int tot = 1,S,T,head[N],to[N],val[N],cst[N],nxt[N],pre[N],dis[N],in[N];
queue <int> q;
il void add_(int x,int y,int z,int c){to[++tot] = y,val[tot] = z,cst[tot] = c,nxt[tot] = head[x],head[x] = tot;}
il void add_edge(int x,int y,int z,int c){add_(x,y,z,c),add_(y,x,0,-c);}
il void spfa()
{
memset(dis,-127,sizeof(int) * (cnt + 1));
q.push(S),dis[S] = 0,in[S] = 1;
while(!q.empty())
{
int x = q.front();
q.pop(),in[x] = 0;
for(int i = head[x],y;i;i = nxt[i])
if(val[i] && dis[y = to[i]] < dis[x] + cst[i])
{
dis[y] = dis[x] + cst[i],pre[y] = i;
if(!in[y]) q.push(y),in[y] = 1;
}
}
}
il void ek()
{
int ans = 0;
while(K--)
{
spfa(),ans += dis[T];
for(int i = T;i != S;i = to[pre[i] ^ 1]) val[pre[i]]--,val[pre[i] ^ 1]++;
printf("%d ",ans);
}
puts("");
}
} g;
void Main()
{
for(int i = 1;i <= n;i++) a[i] = read();
for(int i = 1;i <= n;i++) b[i] = read();
for(int i = 1,x,y,z;i <= m;i++)
{
x = read(),y = read(),z = read() + 2 * (a[x] | b[y]);
p1[x].pb((Edge){x,y,z}),p2[y].pb((Edge){x,y,z});
}
for(int i = 1;i <= n;i++) w1[a[i]].pb(i);
for(int i = 1;i <= n;i++) w2[b[i]].pb(i);
for(int i = 0;i < V;i++)
{
for(int j = 0;j < V;j++) t[j].clear();
for(int j = 0;j < V;j++) t[i | j].pb(j);
for(int j = V - 1;j >= 0 && cnt1[i] < K;j--)
for(int k : t[j])
{
for(int c = w2[k].size() - 1;c >= 0 && cnt1[i] < K;c--) s1[i][++cnt1[i]] = w2[k][c];
if(cnt1[i] == K) break;
}
for(int j = V - 1;j >= 0 && cnt2[i] < K;j--)
for(int k : t[j])
{
for(int c = w1[k].size() - 1;c >= 0 && cnt2[i] < K;c--) s2[i][++cnt2[i]] = w1[k][c];
if(cnt2[i] == K) break;
}
}
for(int i = 1;i <= n;i++)
{
for(Edge j : p1[i]) vis[j.y] = i;
sort(p1[i].begin(),p1[i].end(),cmp1);
for(int j = 1,x = 1,y = 0;j <= K;j++)
{
while(x <= K && vis[s1[a[i]][x]] == i) x++;
if(x <= K && (y == (int)p1[i].size() || 2 * (a[i] | b[s1[a[i]][x]]) > p1[i][y].z)) p[s1[a[i]][x++]].pb(i);
else p[p1[i][y++].y].pb(i);
}
}
memset(vis,0,sizeof(vis));
for(int i = 0;i < V;i++)
{
memcpy(s1[i],s2[i],sizeof(int) * (K + 1));
sort(s1[i] + 1,s1[i] + K + 1);
}
for(int i = 1;i <= n;i++)
{
for(Edge j : p2[i]) vis[j.x] = i;
sort(p2[i].begin(),p2[i].end(),cmp1);
for(int j = 1,x = 1,y = 0;j <= K;j++)
{
while(x <= K && vis[s2[b[i]][x]] == i) x++;
if(x <= K && (y == (int)p2[i].size() || 2 * (a[s2[b[i]][x]] | b[i]) > p2[i][y].z)) used[s2[b[i]][x++]] = i;
else used[p2[i][y++].x] = i;
}
sort(p2[i].begin(),p2[i].end(),cmp2);
for(int j = 1,x = 1,y = 0,k,cur = 0,d;j <= K;j++)
{
while(x <= K && (vis[s1[b[i]][x]] == i || used[s1[b[i]][x]] != i)) x++;
while(y < (int)p2[i].size() && used[p2[i][y].x] != i) y++;
if(x <= K && (y == (int)p2[i].size() || s1[b[i]][x] < p2[i][y].x)) k = s1[b[i]][x++],d = -1;
else k = p2[i][y].x,d = p2[i][y++].z;
while(cur < (int)p[i].size() && p[i][cur] < k) cur++;
if(cur == (int)p[i].size()) break;
if(p[i][cur] == k) e.pb((Edge){k,i,d == -1 ? 2 * (a[k] | b[i]) : d});
}
}
int up = min(min((int)e.size(),2 * K * K),10000);
if(up < (int)e.size())
{
nth_element(e.begin(),e.begin() + up,e.end(),cmp1);
e.resize(up);
}
for(Edge i : e)
{
if(!id1[i.x]) id1[i.x] = ++cnt;
if(!id2[i.y]) id2[i.y] = ++cnt;
g.add_edge(id1[i.x],id2[i.y],1,i.z);
}
g.T = ++cnt;
for(int i = 1;i <= n;i++) if(id1[i]) g.add_edge(0,id1[i],1,0);
for(int i = 1;i <= n;i++) if(id2[i]) g.add_edge(id2[i],cnt,1,0);
g.ek();
}
}
namespace BBB
{
int tot,a[N],b[N],f[M][M],opt[M][M],id1[N],id2[N],p1[M],p2[M],mch1[M],mch2[M],val1[M],val2[M],c1[M],c2[M],p[M];
int head1[N],to1[N * 5],v1[N * 5],nxt1[N * 5],head2[N],to2[N * 5],v2[N * 5],nxt2[N * 5],cnt1[V],cnt2[V],cur1[V],cur2[V],s1[V][M],s2[V][M];
vector <int> t[V],w1[V],w2[V];
map <int,int> mp[N];
void get_rt(int s,int t)
{
int mid = opt[s][t];
if(!mid) return ;
get_rt(s,mid),p[++tot] = mid,get_rt(mid,t);
}
il int get_val(int x,int y)
{
int ret = 2 * (a[x] | b[y]);
if(mp[x].find(y) != mp[x].end()) ret += mp[x][y];
return ret;
}
void Main()
{
for(int i = 1;i <= n;i++) a[i] = read();
for(int i = 1;i <= n;i++) b[i] = read();
for(int i = 1;i <= n;i++) w1[a[i]].pb(i);
for(int i = 1;i <= n;i++) w2[b[i]].pb(i);
for(int i = 0;i < V;i++)
{
for(int j = 0;j < V;j++) t[j].clear();
for(int j = 0;j < V;j++) t[i | j].pb(j);
for(int j = V - 1;j >= 0;j--)
for(int k : t[j])
{
for(int c = w2[k].size() - 1;c >= 0 && cnt1[i] < K;c--) s1[i][cnt1[i]++] = w2[k][c];
for(int c = w1[k].size() - 1;c >= 0 && cnt2[i] < K;c--) s2[i][cnt2[i]++] = w1[k][c];
}
}
for(int i = 1,x,y,z;i <= m;i++)
{
x = read(),y = read(),z = read();
to1[i] = y,v1[i] = z,nxt1[i] = head1[x],head1[x] = i;
to2[i] = x,v2[i] = z,nxt2[i] = head2[y],head2[y] = i;
mp[x][y] = z;
}
for(int T = 1,sum = 0;;T++)
{
int max1 = -1,max2 = -1,s,t,u,v,tmp;
for(int i = 1;i <= n;i++)
if(!id1[i])
for(int c = head1[i],j,v;c;c = nxt1[c])
if(!id2[j = to1[c]] && max1 < (v = 2 * (a[i] | b[j]) + v1[c]))
max1 = v,s = i,t = j;
for(int i = 1,v,p;i <= n;i++)
{
if(id1[i]) continue;
v = a[i];
while(id2[p = s1[v][cur1[v]]]) cur1[v]++;
if(max1 < (tmp = 2 * (v | b[p])))
max1 = tmp,s = i,t = p;
}
for(int i = 1;i < T;i++)
for(int j = 1,d;j < T;j++)
if(max2 < (d = f[i][j] + val1[mch2[j]] + val2[i] - get_val(p1[mch2[j]],p2[j])))
max2 = d,u = i,v = j;
sum += max(max1,max2);
printf("%d ",sum);
if(T == K) break;
if(max1 >= max2)
{
id1[s] = id2[t] = T,p1[T] = s,p2[T] = t;
mch1[T] = mch2[T] = T;
}
else
{
p[tot = 1] = u,get_rt(u,v),p[++tot] = v,v = mch2[v];
for(int i = tot - 1,t;i >= 1;i--)
{
t = mch2[p[i]];
mch1[t] = p[i + 1],mch2[p[i + 1]] = t;
}
id1[c2[u]] = id2[c1[v]] = T,p1[T] = c2[u],p2[T] = c1[v];
mch1[T] = u,mch2[u] = T;
mch2[T] = v,mch1[v] = T;
}
for(int i = 1;i <= T;i++)
for(int j = 1;j <= T;j++)
if(i != j) f[i][j] = get_val(p1[mch2[i]],p2[j]) - get_val(p1[mch2[i]],p2[i]);
else f[i][j] = 0;
for(int i = 1;i <= T;i++)
for(int j = 1;j <= T;j++)
opt[i][j] = 0;
for(int k = 1,v;k <= T;k++)
for(int i = 1;i <= T;i++)
for(int j = 1;j <= T;j++)
if((v = f[i][k] + f[k][j]) > f[i][j])
f[i][j] = v,opt[i][j] = k;
for(int i = 1;i <= T;i++) val1[i] = val2[i] = -1;
for(int i = 1,maxn,p;i <= T;i++)
{
maxn = -1;
for(int c = head1[p1[i]],j,v;c;c = nxt1[c])
if(!id2[j = to1[c]] && maxn < (v = 2 * (a[p1[i]] | b[j]) + v1[c]))
maxn = v,p = j;
if(maxn > val1[i]) val1[i] = maxn,c1[i] = p;
}
for(int i = 1,v,p;i <= T;i++)
{
v = a[p1[i]];
while(id2[p = s1[v][cur1[v]]]) cur1[v]++;
if(val1[i] < (tmp = 2 * (v | b[p]))) val1[i] = tmp,c1[i] = p;
}
for(int i = 1,maxn,p;i <= T;i++)
{
maxn = -1;
for(int c = head2[p2[i]],j,v;c;c = nxt2[c])
if(!id1[j = to2[c]] && maxn < (v = 2 * (a[j] | b[p2[i]]) + v2[c]))
maxn = v,p = j;
if(maxn > val2[i]) val2[i] = maxn,c2[i] = p;
}
for(int i = 1,v,p;i <= T;i++)
{
v = b[p2[i]];
while(id1[p = s2[v][cur2[v]]]) cur2[v]++;
if(val2[i] < (tmp = 2 * (v | a[p]))) val2[i] = tmp,c2[i] = p;
}
}
puts("");
}
}
int main()
{
freopen("transfer.in","r",stdin);
freopen("transfer.out","w",stdout);
n = read(),m = read(),K = read();
if(n <= 300 && m <= 10000 && K <= 300) BBB :: Main();
else AAA :: Main();
return 0;
}
~~~