[A/C 2007] 数据备份 (网络流, 堆)
给你 N 各点的位置和 K 条链, 需要用这些链把 2K 个点连起来, 使得链的总长最短. 可以随意选择要链的点. n=100000.
这道题居然可以用堆......
首先, 不能把区间一股脑加进去, 因为有点可能会被重复连接. 处理方法是这样的: 若选择了第 i 个区间, 那就把 i, 区间 i-1 和区间 i+1 都删除了, 然后加入一个新区间, 和左右区间相连接, 并且将当前区间的值改为 \(len[i-1]+len[i+1]-len[i]\). 这样如果再选这个区间, 就相当于把区间 i 撤消了.
具体证明嘛, 见这个 https://blog.csdn.net/sdogsq/article/details/20614045 , 讲道理我是不想看..
- // luogu-judger-enable-o2
- // luogu-judger-enable-o2
- #include <cstdio>
- using namespace std;
- typedef long long LL;
- const LL maxn=1e5+5, INF=1e18;
- LL n, k, a[maxn];
- struct Node{
- Node(LL x=0, LL y=0){ v=x; chain=y; }
- LL v, chain;
- }node[maxn]; // 维护链长的最小堆
- bool operator <(Node &a, Node &b){ return a.v<b.v; }
- LL cntnode, cntc, ans;
- struct Chain{
- LL l, r, len, node;
- }c[maxn], tmpl, tmpr; // 以左端点编号. len 表示长度. node 表示堆中的哪个点
- void swap(LL &x, LL &y){ LL t=x; x=y; y=t; }
- void swap(LL x, LL y){ // 传进来的是堆中点的编号
- c[node[x].chain].node=y;
- c[node[y].chain].node=x;
- Node tmp=node[x]; node[x]=node[y]; node[y]=tmp;
- }
- void ins(LL now){
- while (now!=1){
- if (node[now]<node[now>>1])
- swap(now, now>>1), now>>=1;
- else break;
- }
- }
- void del(LL now){ // 只是清零并移到最后
- if (now==0) return;
- node[now].v=INF; LL p;
- while ((now<<1)<=cntnode){
- if (now<<1==cntnode||node[now<<1].v<node[now<<1|1].v) p=0; else p=1;
- swap(now, now<<1|p), now=now<<1|p;
- }
- }
- int main(){
- scanf("%lld%lld", &n, &k);
- for (LL i=1; i<=n; ++i) scanf("%lld", &a[i]);
- for (LL i=1; i<n; ++i){
- c[i].l=i-1; c[i].r=i+1; ++cntc;
- node[++cntnode].v=c[i].len=a[i+1]-a[i];
- node[cntnode].chain=i; c[i].node=cntnode; ins(cntnode);
- }
- c[0].len=c[n].len=INF;
- for (LL i=1; i<=k; ++i){
- Chain &tmp=c[node[1].chain]; // 选定长度最小的链
- tmpl=c[tmp.l]; tmpr=c[tmp.r]; // 和它旁边的两条链
- ans+=tmp.len;
- del(1); del(c[tmp.l].node); del(c[tmp.r].node); // 把这三个链代表的点从堆里面删掉
- c[tmpl.l].r=tmpl.r; c[tmpr.r].l=tmpr.l; // 把原来的链变成合并后的链
- tmp.l=tmpl.l; tmp.r=tmpr.r;
- tmp.len=tmpl.len+tmpr.len-tmp.len;
- node[tmp.node].v=tmp.len; // 把原来的点变成新点
- ins(tmp.node);
- }
- printf("%lld\n", ans);
- return 0;
- }
自己还是太 NAIVE 了, 其实根本就不需要从外部访问堆的说, 下面这个大神代码就没有用, 用的是 stl 里面的优先队列 orz.
只要不用外部访问堆, 都可以用 stl~
- #include<iostream>
- #include<cstdio>
- #include<queue>
- #define INF 2000000000
- #define MN 100000
- #define pa pair<long long,int>
- #define mp make_pair
- using namespace std;
- int read()
- {
- int x=0,f=1;char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
- return x*f;
- }
- long long ans=0;
- int n,k,ne[MN+5],la[MN+5],a[MN+5],len[MN+5];
- bool del[MN+5];
- priority_queue<pa,vector<pa>,greater<pa>> q;
- int main()
- {
- n=read();k=read();
- for(int i=1;i<=n;i++)a[i]=read();
- for(int i=1;i<=n+1;i++)la[i+1]=i,ne[i]=i+1;
- la[1]=0;ne[n+1]=0;
- for(int i=2;i<=n;i++)
- q.push(mp(len[i]=a[i]-a[i-1],i));
- len[1]=len[n+1]=INF;
- for(int i=1;i<=k;i++)
- {
- while(del[q.top().second])q.pop();
- ans+=q.top().first;int x=q.top().second;q.pop();
- int a=la[x],b=ne[x];
- del[a]=del[b]=1;
- q.push(mp(len[x]=len[a]+len[b]-len[x],x));
- la[x]=la[a];ne[x]=ne[b];
- ne[la[a]]=x;la[ne[b]]=x;
- }
- cout<<ans;
- return 0;
- }
[A/C 2007] 数据备份 (网络流, 堆)
来源: http://www.bubuko.com/infodetail-2612757.html