n
n
n个点构成的若干棵环套树上,两人依次选边,要求不能与已选的构成环,两人分别尽可能最大化/最小化最终的边权和,直到两人都不能选为止,问此时选出的边权和。
n
≤
1
0
5
nle10^5
n≤105
题解
这是一道结论题,其实结论很好猜,但不好证。
首先,不在环上的边是一定会被选上的,只用考虑环上的边。
手玩一下奇环会发现,把边权排序后,两人为了对自己最有利总会对称地选,所以会剩下中间的边没选;
而偶环类似地可以猜想,最后一定会剩下中间两个的某一个,至于先选哪个,设有两个环中间这两对分别为
l
i
,
r
i
,
l
j
,
r
j
l_i,r_i,l_j,r_j
li,ri,lj,rj,若要选
i
i
i,最小化权值的话,需满足
l
i
+
r
j
≤
l
j
+
r
i
l_i+r_jle l_j+r_i
li+rj≤lj+ri;最大化权值的话,需满足
r
i
+
l
j
≥
l
i
+
r
j
r_i+l_jge l_i+r_j
ri+lj≥li+rj,会发现这两个式子其实是一样的,移项后发现两人其实都是争着选当前
l
i
−
r
i
l_i-r_i
li−ri最小的,排序交替选择即可。
然而同时有若干个奇环和偶环时是否还是如此?可以证明,这样选一定是最优的。
代码
#include<cstdio>#include<cstring>#include<algorithm>usingnamespace std;#define N 100010#define ll long longint v[N], vi[N], vis[N *2], p[N], st[N][2], tot =0;int last[N], nxt[N *2], to[N *2], ls[N *2], len =1;int c[2], a[N], sum =0;struct node {int l, r, s;}cir[2][N], c0[N];voidadd(int x,int y,int l){
to[++len]= y;
nxt[len]= last[x];
ls[len]= l;
last[x]= len;}voiddfs(int k,int fa){
vi[k]=1;for(int i = last[k]; i; i = nxt[i])if(!vis[i]){
vis[i]= vis[i ^1]=1;if(!vi[to[i]]){
st[++tot][0]= k, st[tot][1]= ls[i];dfs(to[i], i);
tot--;}else{int s =1, j = tot;while(to[i]!= k){
s++;if(st[j][0]== to[i])break;
j--;}
s %=2;
cir[s][++c[s]].l = sum +1;
cir[s][c[s]].r = sum +1, cir[s][c[s]].s =1;
j = tot;
a[++sum]= ls[i];while(to[i]!= k){
a[++sum]= st[j][1];
cir[s][c[s]].r++, cir[s][c[s]].s++;if(st[j][0]== to[i])break;
j--;}}}}intcmp(node x, node y){return x.s > y.s;}intmain(){int n, i, j, x;
ll ans =0;scanf("%d",&n);for(i =1; i <= n; i++)scanf("%d",&v[i]);for(i =1; i <= n; i++){scanf("%d",&x);add(i, v[i], x),add(v[i], i, x);
ans += x;}for(i =1; i <= n; i++)if(!vi[i])dfs(i,0);for(i =1; i <= sum; i++) ans -= a[i];for(i =1; i <= c[1]; i++){sort(a + cir[1][i].l, a + cir[1][i].r +1);for(j =0; j < cir[1][i].s /2; j++) ans += a[cir[1][i].l + j]+ a[cir[1][i].r - j];}for(i =1; i <= c[0]; i++){sort(a + cir[0][i].l, a + cir[0][i].r +1);for(j =0; j < cir[0][i].s /2-1; j++) ans += a[cir[0][i].l + j]+ a[cir[0][i].r - j];
c0[i].l = a[cir[0][i].l + j];
c0[i].r = a[cir[0][i].l + j +1];
c0[i].s = c0[i].r - c0[i].l;}sort(c0 +1, c0 + c[0]+1, cmp);for(i =1; i <= c[0];){
ans += c0[i++].l;if(i > c[0])break;
ans += c0[i++].r;}printf("%lld
", ans);return0;}
自我小结
考场上并没有想到列不等式,仅仅猜了假结论导致答案错误,
后面化式子时自然而然地以为另一人从
l
i
−
r
i
l_i-r_i
li−ri最大开始选择,又一次导致了答案错误。