简化题意：一序列，查询区间和$s_{isim j}$已知花费$c_{i,j}$，求知悉所有数最小花费。
- 神仙思路题
- 查询一个区间$isim j$，记前缀和$sum$，则如果在某时候知道了$sum_{i-1}$或者$sum_j$中的任意一个，另一个也可以知道，那么可以选择花费$c_{i,j}$连无向边使其联通。
- 联通的块的前缀和都可以知晓。
- 目标是求所有数，也就是知道所有前缀和就好了。
- 那么，添加0号点后，为了知道所有前缀和，也就只要让$0sim n$这$n+1$个点以最小的代价联通就好了。
- 直接Prim。初态是$dis_0=0$。
- 不要问我为什么。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define dbg(x) cerr << #x << " = " << x <<endl 8 #define dbg2(x,y) cerr<< #x <<" = "<< x <<" "<< #y <<" = "<< y <<endl 9 using namespace std; 10 typedef long long ll; 11 typedef double db; 12 typedef pair<int,int> pii; 13 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 14 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 15 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;} 16 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;} 17 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;} 18 template<typename T>inline T read(T&x){ 19 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 20 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 21 } 22 const int N=2000+7,INF=0x3f3f3f3f; 23 int c[N][N],dis[N],vis[N]; 24 int n; 25 ll ans; 26 27 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout); 28 read(n); 29 for(register int i=1;i<=n;++i)for(register int j=i;j<=n;++j)read(c[i][j]); 30 for(register int i=1;i<=n;++i)dis[i]=c[1][i]; 31 for(register int i=1,tmp=INF,p;i<=n;++i,tmp=INF){ 32 for(register int j=1;j<=n;++j)if(!vis[j]&&MIN(tmp,dis[j]))p=j; 33 ans+=tmp,vis[p]=1; 34 for(register int j=1;j<=n;++j)if(!vis[j])MIN(dis[j],j<p?c[j+1][p]:c[p+1][j]); 35 } 36 return printf("%lld ",ans),0; 37 }
总结：没法总结。瓶颈在于转化建边，遇到区间和（异或）有常用思路是拆为前缀和，像这题手玩可以发现明显查询的区间与区间只会相互包含不会相交，暗示可以转化成为前缀关系更为简便。