首页 > 代码库 > BZOJ 3714: [PA2014]Kuglarz
BZOJ 3714: [PA2014]Kuglarz
Description
魔术师的桌子上有n个杯子排成一行，编号为1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费c_ij元，魔术师就会告诉你杯子i,i+1,…,j底下藏有球的总数的奇偶性。
采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？
Input
第一行一个整数n(1<=n<=2000)。
第i+1行(1<=i<=n)有n+1-i个整数，表示每一种询问所需的花费。其中c_ij（对区间[i,j]进行询问的费用，1<=i<=j<=n,1<=c_ij<=10^9）为第i+1行第j+1-i个数。
Output
输出一个整数，表示最少花费。
题解：
参考小胖的奇偶那道题。
那道题用的并查集维护。
如果知道 i..j 之间奇偶性的话，实际上知道的是 sum[j]-sum[i-1]的奇偶性（sum为前缀和）。
可以用扩展域的并查集维护任意两个sum[i]之间的差值。
有了这个结论，如果全部知道哪些杯底有球，就需要所有的sum之间的关系已知，也就是并查集中所有点都在一个集合中，是一棵树。
所以遍转化成了最小生成树问题。
代码:
Kruskal 10384 ms
#include<cstdio>#include<cstring>#include<algorithm>//by zrt//problem:using namespace std;int n;struct N{ int x,y,w;}map[2005*2005];int tot;bool cmp(N a,N b){ return a.w<b.w;}int f[2005];int get(int x){ return f[x]==x?x:f[x]=get(f[x]);}int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif scanf("%d",&n); for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ scanf("%d",&map[tot].w); map[tot].x=i; map[tot].y=j+1; tot++; } } sort(map,map+tot,cmp); long long cost(0); for(int i=1;i<=n+1;i++) f[i]=i; for(int i=0;i<tot;i++){ if(get(map[i].x)!=get(map[i].y)){ f[get(map[i].x)]=get(map[i].y); cost+=map[i].w; } } printf("%lld\n",cost); return 0;}
Prim 16480 ms
#include<cstdio>#include<cstring>#include<algorithm>#include<queue>//by zrt//problem:using namespace std;int n;int val[2005][2005];struct N{ int x,w; N(int a=0,int b=0){ x=a,w=b; } friend bool operator < (N a,N b){ return a.w>b.w; }};priority_queue<N> q;bool vis[2005];int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif scanf("%d",&n); int x; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ scanf("%d",&x); val[j+1][i]=val[i][j+1]=x; } } long long cost(0); q.push(N(1,0)); int c; n=n+1; while(!q.empty()){ x=q.top().x;c=q.top().w;q.pop(); if(vis[x]) continue; vis[x]=1;cost+=c; for(int i=1;i<=n;i++){ if(!vis[i]){ q.push(N(i,val[x][i])); } } } printf("%lld\n",cost); return 0;}
BZOJ 3714: [PA2014]Kuglarz
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。