关于虚点优化以及【车站分级】题解

虚点优化

虚点优化是关于建边-建图的一种优化策略

其实现就是依靠建立一个虚点(顾名思义就是很虚的点hhh

用来减少边数以达到优化建图效率的目的

上面说了一堆

其实还是举例效果会好一些……

比如一侧有n个点,另一侧有m个点,需要两两之间互相连边,如果按照正常的建边方式,边数显然是n*m,听起来就不是很理想

以n=5,m=4为例

如下图

专心看博客!

如上,每条边的长度为1

看起来就很见鬼

但是可以思考一下

其实可以等效于下图

专心看博客!

上面的边的长度都为1,下面的边长度为0,那么上面的点和下面的点两两之间都可以到达,而且距离都是1

也就是与上上图等价了

而且!

只用了8条边,也就是n+m条边,却达到了n*m条边的效果

——将下面的所有点连向黑点,黑点连向所有上面的点

而黑点也就是这次所讲的主题,虚点

实例应用——NOIP2013车站分级

一条单向的铁路线上,依次有编号为 1, 2, …, n1,2,…,n 的 nn 个火车站。每个火车站都有一个级别,最低为 11 级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 xx ,则始发站、终点站之间所有级别大于等于火车站 xx 的都必须停靠。(注意:起始站和终点站自然也算作事先已知需要停靠的站点)

例如,下表是 55 趟车次的运行情况。其中,前 44 趟车次均满足要求,而第 55 趟车次由于停靠了 33 号火车站( 22级)却未停靠途经的 66 号火车站(亦为 22 级)而不满足要求。

专心看博客!

现有 m 趟车次的运行情况(全部满足要求),试推算这 n 个火车站至少分为几个不同的级别。

对于20% 的数据 1 ≤ n, m ≤ 101≤n,m≤10 ;

对于 50% 的数据, 1 ≤ n, m ≤ 1001≤n,m≤100 ;

对于 100% 的数据, 1 ≤ n, m ≤ 10001≤n,m≤1000 。

关于这题,很显然能找出,在一趟车次中,所有停靠的车站的级数大于没有停靠的车站的级数

那么就是显然的拓扑排序了

但是重点按照正常方式建图是效率最坏时是O((N/2)^2*M),即M趟车次都是从第一个车站到最后一个车站,且停靠站数=不停靠站数=N/2

那么问题就很大了,在2013年时,NOIP评测机并招不住那么大的运算量(所以那时候几乎全场爆炸

但是你会发现,这题刚好能够用到虚点优化

在建图时,对于每趟车次,都是若干个点与若干个点要两两连边的情况

所以最多总共需要(N/2)^2*M条边,而这个(N/2)^2,如果用虚点来做,只用N条边就可以完成了

而建图的效率也成功降为O(N*M)

评测机完全招的住

至此,虚点优化被冠上黑科技的名号

以下为该题代码

#include<cstdio>
#include<cctype>
#include<cstring>
#define maxn 2005
#define maxe 2000005

inline int max(int x,int y) {if (x>y) return x;return y;}
inline int read() {
    int x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch)) f^=(ch=='-'),ch=getchar();
    while (isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    if (f) return -x;return x;
}
inline void OPENFILE() {
#ifndef ONLINE_JUDGE
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
#endif
}

int n,m,Count,ans;//Count 虚点计数
int lnk[maxn],nxt[maxe],son[maxe],w[maxe],tot;
int f[maxn];//点的入度
int que[maxn],head,tail,S[maxn];//队列,队列首,队列尾,点的深度(注意虚点与其子节点的连边边权为0
bool vis[maxn];
inline void Add_e(int x,int y,int z) {son[++tot]=y,nxt[tot]=lnk[x],lnk[x]=tot,w[tot]=z;}
void topo() {
    memset(que,0,sizeof(que)),head=tail=0;
    for (int i=1;i<=Count;i++) if (!f[i]) que[++tail]=i,S[i]=(i<=n);//如果入度为0的点是虚点的话那么它的深度就是0否则为1
    while (head^tail) {
        int now=que[++head];
        ans=max(ans,S[now]);
        for (int i=lnk[now];i;i=nxt[i]) {
            S[son[i]]=max(S[son[i]],S[now]+w[i]);//深度按照边权计算,而不是单纯的+1,因为不可以将虚点算入深度内
            if (!(--f[son[i]])) que[++tail]=son[i];
        }
    }
}
int main() {
    OPENFILE();
    n=Count=read(),m=read();
    for (int i=1,x,L=0,R=0;i<=m;i++) {//建边优化!
        ++Count,x=read();
        for (int i=1,rint;i<=x;i++){
            vis[rint=read()]=1;
            if (i==1) L=rint;else if (i==x) R=rint;
        }
        for (int i=L;i<=R;i++) if (vis[i]) Add_e(Count,i,1),f[i]++;else Add_e(i,Count,0),f[Count]++;//虚点与其子节点的连边边权为0
        memset(vis,0,sizeof(vis));
    }
    topo();
    printf("%d\n",ans);
    return 0;
}

Okeydokey!

如有问题可以在下方评论区提问或指出,Dua的

“关于虚点优化以及【车站分级】题解”的3个回复

  1. Clomid 2 Par Aliment cialis 20mg for sale Strattera Online Uk Scam Vendita Viagra Farmacia Kamagra Special Offer Commander Kamagra Original Coumadin For Sale Online Pharmacy Malegra cialis el pais Real Best Viagra Online Pharmacy Buy Viagra Online Australia Cephalexin Reactions For Dogs Cialis 5mg Tadalafil Lilly Zithromax Rhinopharyngite viagra Chewable Kamagra Cod Generic Isotretinoin Buy Levitra Overnight Delivery cialis from canada Propecia Paginas Amarillas Buy Roche Accutane Online Uk Cytotec Misoprostol Grossesse Acquistare Kamagra Miglior Sito Acquisto Viagra Con Bonifico cheapest cialis For Sale Hydrochlorothiazide Female Viagra For Sale viagra Amoxicillin Stomach Canadian Pharmacies For Cialis Cheap Zithromax Online

  2. Official Canadian Pharmacy Viagra Como Comprar priligy farmacias chile Kamagra Legal Kamagra Consegna Veloce Francia Viagra Legal Kaufen Ohne Rezept Propecia 100mg Cialis Impuissance Masculine Dove Acquistare Cialis Sicuro achat en ligne viagra Female Cialis Samples Levitra Tab Keflex And Conjunctivits Zithromax Pills viagra Buy Celexa Online Cheap 20 Mg Cialis Side Effects cheapest cialis Cheap Generic Drugs From India Levitra Giovani Levitra Prix Maroc order levitra at walmart Viagra Cheap Usa Real Zentel Echinococcosis Online Tablet Overseas Priligy Scheda Tecnica Propecia Espana Disfuncion Erectil cialis without a doctor’s prescription Kamagra Australia Mastrcard Tadalis Sx France Levothyroxine For Sale Online

发表评论