曼哈頓最小生成樹

莫濤大神的論文
曼哈頓距離最小生成樹問題可以簡(jiǎn)述如下：
給定二維平面上的N個(gè)點(diǎn)，在兩點(diǎn)之間連邊的代價(jià)為其曼哈頓距離悔橄，求使所有點(diǎn)連通的最小代價(jià)蒸其。

曼哈頓距離：給定二維平面上的N個(gè)點(diǎn)帝美，在兩點(diǎn)之間連邊的代價(jià)碍彭。（即distance(P1,P2) = |x1－x2|+|y1－y2|）

樸素的算法可以用O(n^2)的Prim，或者處理出所有邊做Kruskal悼潭，但在這里總邊數(shù)有O( n^2)條庇忌，所以Kruskal的復(fù)雜度變成了O( n^2logn)。

而莫濤的算法時(shí)間復(fù)雜度是nlogn

莫隊(duì)算法步驟

算法步驟：
先將點(diǎn)按x坐標(biāo)升序排序舰褪；
以任一一個(gè)點(diǎn)為端點(diǎn)皆疹，將平面分為八塊，每塊占45度角占拍，那么在生成樹的最優(yōu)解中略就，每個(gè)塊與這個(gè)點(diǎn)至多有一條邊，即一個(gè)點(diǎn)最多分別向八個(gè)方向最近的點(diǎn)連接一條邊晃酒，一條邊兩個(gè)點(diǎn)共用表牢，同時(shí)，有四個(gè)方向是兩兩對(duì)稱的贝次，所以只需要求出四塊（一般求第一象限和第四象限）所以最后邊數(shù)為4 * n崔兴。

B - 曼哈頓最小生成樹
題意;
求曼哈頓最小生成樹的第n-k條邊的權(quán)值
題解：
實(shí)現(xiàn)一：線段樹＋莫隊(duì)算法

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=10010;
const int MAXE=4*MAXN;
/*Kruskal  Algorithm*/
int parent[MAXN];
int father(int u)
{
    while(parent[u]!=u)
    {
        parent[u]=parent[parent[u]];
        u=parent[u];
    }
    return u;
}
bool connect(int u,int v)
{
    int fu=father(u);
    int fv=father(v);
    if(fv==fu) return false;
    parent[fu]=fv;
    return true;
}
struct Edge
{
    int u,v,w;
    Edge(){}
    Edge(int u,int v,int w):u(u),v(v),w(w){}
    bool operator<(const Edge &ee)const
    {
        return w<ee.w;
    }
};
Edge edge[MAXE];
int cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt++]=Edge(u,v,val);
}
/*線段樹  */
struct Point
{
    int x,y,id;
    bool operator<(const Point &t) const
    {
        if(x==t.x) return y<t.y;
        return x<t.x;
    }
};
Point point[MAXN];
const int INF=0x3f3f3f3f;
struct Node
{
    int len,id;
};
Node tree[(MAXN+20)<<2];
void build(int l,int r,int rt)//init tree
{
    tree[rt].len=INF;
    tree[rt].id=-1;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}
void update(int l,int r,int rt,Point &p,int pos)//push Point into tree
{
    if(l==r)
    {
        if(tree[rt].len>p.x+p.y)//be careful
        {
            tree[rt].len=p.x+p.y;
            tree[rt].id=p.id;
        }
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(l,mid,rt<<1,p,pos);
    else update(mid+1,r,rt<<1|1,p,pos);
    if(tree[rt<<1].len<tree[rt<<1|1].len)
    {
        tree[rt].len=tree[rt<<1].len;
        tree[rt].id=tree[rt<<1].id;
    }
    else
    {
        tree[rt].len=tree[rt<<1|1].len;
        tree[rt].id=tree[rt<<1|1].id;
    }
}
Node query(int l,int r,int L,int R,int rt)//從大于point[i].y-point[i].x的節(jié)點(diǎn)找最小值
{
    if(l==L&&r==R) return tree[rt];
    int mid=(l+r)>>1;
    if(R<=mid) return query(l,mid,L,R,rt<<1);
    else if(L>=mid+1) return query(mid+1,r,L,R,rt<<1|1);
    else
    {
        Node t1=query(l,mid,L,mid,rt<<1);
        Node t2=query(mid+1,r,mid+1,R,rt<<1|1);
        if(t1.len<t2.len) return t1;
        else return t2;
    }
}
int cpy[MAXN],arr[MAXN];
void solve(int n)
{
    sort(point+1,point+1+n);
    for(int i=1;i<=n;i++)
    {
        arr[i]=point[i].y-point[i].x;
        cpy[i]=arr[i];
    }
    sort(cpy+1,cpy+1+n);
    int cc=unique(cpy+1,cpy+1+n)-cpy;
    for(int i=1;i<=n;i++)
    {
        arr[i]=lower_bound(cpy+1,cpy+cc,arr[i])-cpy;//離散化
    }
    build(1,n,1);
    for(int i=n;i>0;i--)
    {
        int len=point[i].x+point[i].y;
        Node t=query(1,n,arr[i],n,1);
        if(t.id!=-1) addEdge(point[i].id,t.id,abs(len-t.len));
        update(1,n,1,point[i],arr[i]);
    }
}
/*Kruskal  Algorithm*/
int kruskal_mst(int k,int n)
{
    int u,v,sum=0;
    sort(edge,edge+cnt);
    for(int i=0;i<cnt;i++)
    {
        u=edge[i].u;v=edge[i].v;
        if(connect(u,v))
        {
            sum++;
            if(sum==n-k) return edge[i].w;
        }
    }
}
int main()
{
    int n,k;
    cnt=0;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&point[i].x,&point[i].y);
        point[i].id=i;
    }
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
    }
    solve(n);//第一象限左上角
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y;
    solve(n);//第一象限右下角
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y,swap(point[i].x,point[i].y);
    solve(n);//第四象限左下角
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y;
    solve(n);//第四象限右上角
    printf("%d\n",kruskal_mst(k,n));
}

實(shí)現(xiàn)二：
樹狀數(shù)組＋莫隊(duì)算法

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=100010;
const int MAXE=MAXN*4;
const int INF=0x3f3f3f3f;
/*kruskal alrorithm*/
int father[MAXN],n;
int parent(int u)
{
    while(father[u]!=u)
    {
        father[u]=father[father[u]];
        u=father[u];
    }
    return u;
}
bool connect(int u,int v)
{
    int fu=parent(u);
    int fv=parent(v);
    if(fu==fv) return false;
    father[fu]=fv;
    return true;
}
struct Point
{
    int x,y,id;//id is for union_found
    bool operator <(const Point &p) const
    {
        if(x==p.x) return y<p.y;
        return x<p.x;
    }
};
Point point[MAXN];
/*數(shù)狀數(shù)組*/
struct Node
{
    int len,id;//len is to find min(x+y), id is for union_found
    void init(){len=INF;id=-1;}
};
Node c[MAXN<<2];
/*倒敘的樹狀數(shù)組，求的是后綴*/
void add(int x,Point &p)//push point into tree
{
    int len=p.x+p.y;
    while(x>0)
    {
        if(c[x].len>len)
        {
            c[x].id=p.id;
            c[x].len=len;
        }
        x-=x&(-x);
    }
}
/*在區(qū)間[x,y]求最小值*/
Node query(int x,int y)//從大于point[i].y-point[i].x的節(jié)點(diǎn)找最小值
{
    Node t;t.init();
    while(x<=y)
    {
        if(t.len>c[x].len)
        {
            t=c[x];
        }
        x+=x&(-x);
    }
    return t;
}
struct Edge
{
    int u,v,w;
    Edge(){}
    Edge(int u,int v,int w):u(u),v(v),w(w){}
    bool operator <(const Edge &ee) const
    {
        return w<ee.w;
    }
};
Edge edge[MAXE];
int cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt++]=Edge(u,v,val);
}
int cpy[MAXN],arr[MAXN];
void solve(int n)
{
    sort(point+1,point+1+n);
    for(int i=1;i<=n;i++)
    {
        arr[i]=cpy[i]=point[i].y-point[i].x;
    }
    sort(cpy+1,cpy+1+n);
    int cc=unique(cpy+1,cpy+1+n)-cpy;
    for(int i=1;i<=n;i++)
    {
        arr[i]=lower_bound(cpy+1,cpy+cc,arr[i])-cpy;
    }
    for(int i=1;i<=cc;i++) c[i].init();
    for(int i=n;i>0;i--)
    {
        Node t=query(arr[i],cc);
        if(t.id!=-1) addEdge(point[i].id,t.id,abs(point[i].x+point[i].y-t.len));
        add(arr[i],point[i]);
    }
}
long long kruskal_mst(int k)
{
    int u,v;
    long long sum=0;
    sort(edge,edge+cnt);
    for(int i=0;i<cnt;i++)
    {
        u=edge[i].u;v=edge[i].v;
        if(connect(u,v))
        {
            sum++;
            if(sum==n-k) return edge[i].w;
        }
    }
    return sum;
}
int main()
{
    int k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&point[i].x,&point[i].y);
        point[i].id=i;
    }
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
    }
    cnt=0;
    solve(n);
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y;
    solve(n);
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y,swap(point[i].x,point[i].y);
    solve(n);
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y;
    solve(n);
    printf("%lld\n",kruskal_mst(k));
}

C - Another Minimum Spanning Tree
題意：
求解曼哈頓最小生成樹
線段樹＋莫隊(duì)算法

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=100010;
const int MAXE=4*MAXN;
/*Kruskal  Algorithm*/
int parent[MAXN];
int father(int u)
{
    while(parent[u]!=u)
    {
        parent[u]=parent[parent[u]];
        u=parent[u];
    }
    return u;
}
bool connect(int u,int v)
{
    int fu=father(u);
    int fv=father(v);
    if(fv==fu) return false;
    parent[fu]=fv;
    return true;
}
struct Edge
{
    int u,v,w;
    Edge(){}
    Edge(int u,int v,int w):u(u),v(v),w(w){}
    bool operator<(const Edge &ee)const
    {
        return w<ee.w;
    }
};
Edge edge[MAXE];
int cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt++]=Edge(u,v,val);
}
/*線段樹  */
struct Point
{
    int x,y,id;
    bool operator<(const Point &t) const
    {
        if(x==t.x) return y<t.y;
        return x<t.x;
    }
};
Point point[MAXN];
const int INF=0x3f3f3f3f;
struct Node
{
    int len,id;
};
Node tree[(MAXN+20)<<2];
void build(int l,int r,int rt)//init tree
{
    tree[rt].len=INF;
    tree[rt].id=-1;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
}
void update(int l,int r,int rt,Point &p,int pos)//push Point into tree
{
    if(l==r)
    {
        if(tree[rt].len>p.x+p.y)
        {
            tree[rt].len=p.x+p.y;
            tree[rt].id=p.id;
        }
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(l,mid,rt<<1,p,pos);
    else update(mid+1,r,rt<<1|1,p,pos);
    if(tree[rt<<1].len<tree[rt<<1|1].len)
    {
        tree[rt].len=tree[rt<<1].len;
        tree[rt].id=tree[rt<<1].id;
    }
    else
    {
        tree[rt].len=tree[rt<<1|1].len;
        tree[rt].id=tree[rt<<1|1].id;
    }
}
Node query(int l,int r,int L,int R,int rt)//從大于point[i].y-point[i].x的節(jié)點(diǎn)找最小值
{
    if(l==L&&r==R) return tree[rt];
    int mid=(l+r)>>1;
    if(R<=mid) return query(l,mid,L,R,rt<<1);
    else if(L>=mid+1) return query(mid+1,r,L,R,rt<<1|1);
    else
    {
        Node t1=query(l,mid,L,mid,rt<<1);
        Node t2=query(mid+1,r,mid+1,R,rt<<1|1);
        if(t1.len<t2.len) return t1;
        else return t2;
    }
}
int cpy[MAXN],arr[MAXN];
void solve(int n)
{
    sort(point+1,point+1+n);
    for(int i=1;i<=n;i++)
    {
        arr[i]=point[i].y-point[i].x;
        cpy[i]=arr[i];
    }
    sort(cpy+1,cpy+1+n);
    int cc=unique(cpy+1,cpy+1+n)-cpy;//離散化
    for(int i=1;i<=n;i++)
    {
        arr[i]=lower_bound(cpy+1,cpy+cc,arr[i])-cpy;
    }
    build(1,n,1);
    for(int i=n;i>0;i--)
    {
        int len=point[i].x+point[i].y;
        Node t=query(1,n,arr[i],n,1);
        if(t.id!=-1) addEdge(point[i].id,t.id,abs(len-t.len));
        update(1,n,1,point[i],arr[i]);
    }
}
/*Kruskal  Algorithm*/
int kruskal_mst(int n)
{
    int u,v;
    long long sum=0;
    sort(edge,edge+cnt);
    for(int i=0;i<cnt;i++)
    {
        u=edge[i].u;v=edge[i].v;
        if(connect(u,v))
        {
            sum+=(long long) edge[i].w;
        }
    }
    return sum;
}
int main()
{
    int n,cas=1;
    while(scanf("%d",&n)!=EOF,n){
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&point[i].x,&point[i].y);
        point[i].id=i;
    }
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
    }
    solve(n);
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y;
    solve(n);
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y,swap(point[i].x,point[i].y);
    solve(n);
    for(int i=1;i<=n;i++)
        point[i].y=-point[i].y;
    solve(n);
    printf("Case %d: Total Weight = %lld\n",cas++,kruskal_mst(n));
    }
}

樹狀數(shù)組＋莫隊(duì)算法

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=100010;
const int MAXE=MAXN*4;
const int INF=0x3f3f3f3f;
/*kruskal alrorithm*/
int father[MAXN],n;
int parent(int u)
{
    while(father[u]!=u)
    {
        father[u]=father[father[u]];
        u=father[u];
    }
    return u;
}
bool connect(int u,int v)
{
    int fu=parent(u);
    int fv=parent(v);
    if(fu==fv) return false;
    father[fu]=fv;
    return true;
}
struct Point
{
    int x,y,id;//id is for union_found
    bool operator <(const Point &p) const
    {
        if(x==p.x) return y<p.y;
        return x<p.x;
    }
};
Point point[MAXN];
/*數(shù)狀數(shù)組*/
struct Node
{
    int len,id;//len is to find min(x+y), id is for union_found
    void init(){len=INF;id=-1;}
};
Node c[MAXN<<2];
/*倒敘的樹狀數(shù)組浊闪，求的是后綴*/
void add(int x,Point &p)//push point into tree
{
    int len=p.x+p.y;
    while(x>0)
    {
        if(c[x].len>len)
        {
            c[x].id=p.id;
            c[x].len=len;
        }
        x-=x&(-x);
    }
}
/*在區(qū)間[x,y]求最小值*/
Node query(int x,int y)//從大于point[i].y-point[i].x的節(jié)點(diǎn)找最小值
{
    Node t;t.init();
    while(x<=y)
    {
        if(t.len>c[x].len)
        {
            t=c[x];
        }
        x+=x&(-x);
    }
    return t;
}
struct Edge
{
    int u,v,w;
    Edge(){}
    Edge(int u,int v,int w):u(u),v(v),w(w){}
    bool operator <(const Edge &ee) const
    {
        return w<ee.w;
    }
};
Edge edge[MAXE];
int cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt++]=Edge(u,v,val);
}
int cpy[MAXN],arr[MAXN];
void solve(int n)
{
    sort(point+1,point+1+n);
    for(int i=1;i<=n;i++)
    {
        arr[i]=cpy[i]=point[i].y-point[i].x;
    }
    sort(cpy+1,cpy+1+n);
    int cc=unique(cpy+1,cpy+1+n)-cpy;
    for(int i=1;i<=n;i++)
    {
        arr[i]=lower_bound(cpy+1,cpy+cc,arr[i])-cpy;
    }
    for(int i=1;i<=cc;i++) c[i].init();
    for(int i=n;i>0;i--)
    {
        Node t=query(arr[i],cc);
        if(t.id!=-1) addEdge(point[i].id,t.id,abs(point[i].x+point[i].y-t.len));
        add(arr[i],point[i]);
    }
}
long long kruskal_mst()
{
    int u,v;
    long long sum=0;
    sort(edge,edge+cnt);
    for(int i=0;i<cnt;i++)
    {
        u=edge[i].u;v=edge[i].v;
        if(connect(u,v))
        {
            sum+=(long long) edge[i].w;
        }
    }
    return sum;
}
int main()
{
    int cas=1;
    while(scanf("%d",&n)!=EOF,n)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&point[i].x,&point[i].y);
            point[i].id=i;
        }
        for(int i=1;i<=n;i++)
        {
            father[i]=i;
        }
        cnt=0;
        solve(n);
        for(int i=1;i<=n;i++)
            point[i].y=-point[i].y;
        solve(n);
        for(int i=1;i<=n;i++)
            point[i].y=-point[i].y,swap(point[i].x,point[i].y);
        solve(n);
        for(int i=1;i<=n;i++)
            point[i].y=-point[i].y;
        solve(n);
        printf("Case %d: Total Weight = %lld\n",cas++,kruskal_mst());
    }
}

最后編輯于：2017.12.10 07:02:06

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末恼布，一起剝皮案震驚了整個(gè)濱河市螺戳，隨后出現(xiàn)的幾起案子搁宾，更是在濱河造成了極大的恐慌，老刑警劉巖倔幼，帶你破解...
沈念sama閱讀 218,941評(píng)論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件盖腿，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡损同，警方通過查閱死者的電腦和手機(jī)翩腐，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,397評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來膏燃，“玉大人茂卦，你說我怎么就攤上這事∽榱ǎ” “怎么了等龙？”我有些...
開封第一講書人閱讀 165,345評(píng)論 0贊 356
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵处渣，是天一觀的道長(zhǎng)。經(jīng)常有香客問我蛛砰，道長(zhǎng)罐栈，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,851評(píng)論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任旧蛾，我火速辦了婚禮誓焦，結(jié)果婚禮上汁蝶，老公的妹妹穿的比我還像新娘。我一直安慰自己柑贞，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,868評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布聂抢。她就那樣靜靜地躺著凌外，像睡著了一般。火紅的嫁衣襯著肌膚如雪涛浙。梳的紋絲不亂的頭發(fā)上康辑，一...
開封第一講書人閱讀 51,688評(píng)論 1贊 305
城市分裂傳說
那天，我揣著相機(jī)與錄音轿亮，去河邊找鬼疮薇。笑死，一個(gè)胖子當(dāng)著我的面吹牛我注，可吹牛的內(nèi)容都是我干的按咒。我是一名探鬼主播，決...
沈念sama閱讀 40,414評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼但骨，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼励七！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起奔缠，我...
開封第一講書人閱讀 39,319評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤掠抬，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后校哎，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體两波，經(jīng)...
沈念sama閱讀 45,775評(píng)論 1贊 315
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,945評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年闷哆，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了腰奋。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 40,096評(píng)論 1贊 350
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡抱怔，死狀恐怖劣坊，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情屈留，我是刑警寧澤局冰，帶...
沈念sama閱讀 35,789評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布括儒，位于F島的核電站，受9級(jí)特大地震影響锐想，放射性物質(zhì)發(fā)生泄漏帮寻。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,437評(píng)論 3贊 331
男人毒藥：我在死后第九天來索命
文/蒙蒙一赠摇、第九天我趴在偏房一處隱蔽的房頂上張望固逗。院中可真熱鬧，春花似錦藕帜、人聲如沸烫罩。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,993評(píng)論 0贊 22
一樁弒父案洽故，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽贝攒。三九已至，卻和暖如春时甚，著一層夾襖步出監(jiān)牢的瞬間隘弊，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,107評(píng)論 1贊 271
情欲美人皮
我被黑心中介騙來泰國打工荒适，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留梨熙，地道東北人。一個(gè)月前我還...
沈念sama閱讀 48,308評(píng)論 3贊 372
代替公主和親
正文我出身青樓刀诬，卻偏偏與公主長(zhǎng)得像咽扇，于是被迫代替她去往敵國和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子陕壹，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,037評(píng)論 2贊 355

曼哈頓最小生成樹

推薦閱讀更多精彩內(nèi)容