时间原因，被一个唐诗问题困扰，导致没有来得及改昨天的 G。
F. Simons and Reconstructing His Roads
必定为多个欧拉回路。考虑没有不能删的限制，且只有一个欧拉回路的情况（易见回路间互不影响）。
通过大眼观察，假设每个格子的贡献为上左减去下右，则总权值为每个格子的贡献之和。
有不能删的边时，若其靠边，则代表一个格子不能删，否则代表相邻两个格子决策相同。
使用并查集维护即可，时间复杂度 \(O(\sum nm)\)。
注：因为 \(w+v-w-v\) 爆 int wa 了一发。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
const int mod=1e9+7;
#define inf 1e9
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}
#define ll long long
int n,m,T,w[maxn],v[maxn],P[maxn],Q[maxn];
#define calc(x,y) (x-1)*m+y
//inline int calc(int x,int y){return (x-1)*m+y;}
int F[maxn],ok[maxn];ll Sum[maxn];
inline int find(int x){return F[x]==x?x:F[x]=find(F[x]);}
inline void merge(int x,int y){
// printf("merge %d %d\n",x,y);x=find(x),y=find(y);if(x==y)return;F[y]=x;Sum[x]+=Sum[y];ok[x]&=ok[y];
}
inline void solve(){n=read(),m=read();for(int i=1;i<n;i++)for(int j=1;j<=m;j++)w[calc(i,j)]=read();for(int i=1;i<=n;i++)for(int j=1;j<m;j++)v[calc(i,j)]=read();for(int i=1;i<n;i++,getchar())for(int j=1;j<=m;j++)P[calc(i,j)]=getchar()-'0';for(int i=1;i<=n;i++,getchar())for(int j=1;j<m;j++)Q[calc(i,j)]=getchar()-'0';for(int i=1;i<n;i++)for(int j=1;j<m;j++){int id=calc(i,j);
// printf("i=%d j=%d id=%d\n",i,j,id);F[id]=id;ok[id]=1;Sum[id]=0ll+w[id]+v[id]-w[calc(i,j+1)]-v[calc(i+1,j)];if(j==1&&!P[id])ok[id]=0;if(i==1&&!Q[id])ok[id]=0;if(j==m-1&&!P[calc(i,j+1)])ok[id]=0;if(i==n-1&&!Q[calc(i+1,j)])ok[id]=0;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(i<n&&j>1&&j<m&&!P[calc(i,j)])merge(calc(i,j-1),calc(i,j));if(j<m&&i>1&&i<n&&!Q[calc(i,j)])merge(calc(i-1,j),calc(i,j));}ll ans=0;for(int i=1;i<n;i++)for(int j=1;j<m;j++){int id=calc(i,j);if(find(id)!=id)continue;
// printf("i=%d j=%d sum=%lld ok=%d\n",i,j,Sum[id],ok[id]);if(ok[id])ans+=max(0ll,Sum[id]);}printf("%lld\n",ans);
}
int main(){T=read();while(T--)solve();return 0;
}
/*
1
3 4
13 7 6 -12
3 -5 12 -6
-3 10 -15
-5 8 -11
10 0 -5
1111
0110
110
101
010
*/
线性建笛卡尔树
放一个小根笛卡尔树的代码，很玄妙。
点击查看代码
for(int i=1;i<=n;i++){cur=top;while(cur&&p[st[cur]]>p[i])cur--;if(cur)rs[st[cur]]=i;if(cur<top)ls[i]=st[cur+1];st[++cur]=i;top=cur;
}
Codeforces Round 1091 (Div. 2) and CodeCraft 26
太 tm 难了，8！