首先看到这题， 由于要最大， 肯定是求最大生成树

那么 o(n2) dfs 求任意点对之间的最小边是可以想到的

但是看看数据范围肯定TLE

于是暴力出来咯， 不过要注意query的时候判断的时候要 m+-1 但是递归下去要用m ， 可以画图举特例分析

1AC 代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<vector>

#include<queue>

#include<stack>

#include<map>

#include<set>

#include<string>

#include<iomanip>

#include<ctime>

#include<cctype>

#include<algorithm>

#ifdef WIN32

#define AUTO "%I64d"

#else

#define AUTO "%lld"

#endif

using namespace std;

#define smin(x,tmp) x=min((x),(tmp))

const int INF=0x3f3f3f3f;

const int maxn=;

const int maxm=;

int fa[maxn];

int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }

inline bool union_find(int x,int y)

{

    int t1=find(x),t2=find(y);

    if(t1==t2) return false;

    fa[t2]=t1;

    return true;

}

map <pair<int,int>,int> g;

struct Edge

{

    int to,next;

    int val;

}edge[maxm<<];

int head[maxn];

int maxedge;

inline void addedge(int u,int v,int c)

{

    edge[++maxedge]=(Edge){v,head[u],c};

    head[u]=maxedge;

    edge[++maxedge]=(Edge){u,head[v],c};

    head[v]=maxedge;

    g[make_pair(u,v)]=c;

    g[make_pair(v,u)]=c;

}

struct Road

{

    int from,to;

    int cost;

    bool operator < (const Road t) const

    {

        return cost>t.cost;// querying the Biggest MST !!!!

    }

}road[maxm];

int n,m;

int f[maxn],son[maxn],size[maxn],depth[maxn];

int top[maxn],id[maxn],rid[maxn];

int maxnode;//for segment tree (one-demensional array)

int dfs1(int u,int father,int deep)

{

    f[u]=father,size[u]=,depth[u]=deep;

    for(int i=head[u];~i;i=edge[i].next)

    {

        int v=edge[i].to;

        if(v==father) continue;

        size[u]+=dfs1(v,u,deep+);

        if(!son[u]||size[son[u]]<size[v]) son[u]=v;

    }

    return size[u];

}

void dfs2(int u,int tp)

{

    top[u]=tp;id[u]=++maxnode;rid[maxnode]=u;// non de mixer la id-rid !!

    if(son[u]) dfs2(son[u],tp);

    for(int i=head[u];~i;i=edge[i].next)

    {

        int v=edge[i].to;

        if(v==f[u]||v==son[u]) continue;

        dfs2(v,v);

    }

}

int tree[maxn<<];//min

void build(int root,int l,int r)

{

    if(r-l==)

    {

        tree[root]=g[make_pair(rid[l],rid[r])];

        return;

    }

    int m=(l+r)>>;

    build(root<<,l,m);

    build(root<<|,m,r);

    tree[root]=min(tree[root<<],tree[root<<|]);

}

int query(int root,int l,int r,int x,int y)//query min

{

    if(x==y) return INF;//must!! when query the same node !!!!!!

    if(x<=l&&r<=y) return tree[root];

    int m=(l+r)>>;

    int t1=INF,t2=INF;

    if(x<=m-&&l<=y) t1=query(root<<,l,m,x,y);//here too, use x<=m-1 in case stucking at m

    if(y>=m+&&r>=x) t2=query(root<<|,m,r,x,y);//be conscious of m or m+1, query m but judge m+1

    return min(t1,t2);

}

int Find(int u,int v)//find min

{

    int t1=top[u],t2=top[v];

    int ret=INF;

    while(t1^t2)

    {

        if(depth[t1]<depth[t2]) swap(t1,t2),swap(u,v);

        smin(ret,query(,,maxnode,id[t1],id[u]));

        smin(ret,g[make_pair(t1,f[t1])]);

        u=f[t1];

        t1=top[u];

    }

    if(depth[u]<depth[v]) swap(u,v);

    return min(ret,query(,,maxnode,id[v],id[u]));

}

inline void init()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++) scanf("%d%d%d",&road[i].from,&road[i].to,&road[i].cost);

    for(int i=;i<=n;i++) fa[i]=i;

    memset(head,-,sizeof(head));

    maxedge=-;

}

void kruskal()

{

    sort(road+,road+m+);

    int pos=,tot=;

    while(pos<=m && tot^(n-))

    {

        if(union_find(road[pos].from,road[pos].to)) tot++,addedge(road[pos].from,road[pos].to,road[pos].cost);

        pos++;

    }

}

bool vis[maxn];//for union_find

void build_forest()

{

    for(int i=;i<=n;i++)

    {

        int father=find(i);

        if(!vis[father])

        {

            vis[father]=true;

            dfs1(father,,);

            dfs2(father,father);

        }

    }

    build(,,maxnode);

}

int main()

{

    freopen("truck.in","r",stdin);

    freopen("truck.out","w",stdout);

    init();

    kruskal();

    build_forest();

    int q;

    scanf("%d",&q);

    while(q--)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        if(find(x)^find(y)) printf("-1\n");

        else printf("%d\n",Find(x,y));

    }

    return ;

}

但是NOIP正解一定不是链剖， 此题要用到 LCA 的 ST 倍增算法， 并且属于精确的查询，没有重叠部分， 可以用sum等进行替换， 边dfs边更新

用 f[i][j] = f[f[i][j-1]][j-1] 保存 i 前面的第2i 节点， 与普通 RMQ 不同

用 dp[i][j] = min ( dp[i][j-1] , dp[f[i][j-1]][j-1] ) 来维护倍增的最小值 （ 当然 sum 也一样 ， 因为精确求范围， 满足区间加 ）

AC代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<vector>

#include<queue>

#include<stack>

#include<map>

#include<set>

#include<string>

#include<iomanip>

#include<ctime>

#include<cctype>

#include<algorithm>

#ifdef WIN32

#define AUTO "%I64d"

#else

#define AUTO "%lld"

#endif

using namespace std;

#define smin(x,tmp) x=min((x),(tmp))

#define smax(x,tmp) x=max((x),(tmp))

const int INF=0x3f3f3f3f;

const int maxn=;

const int maxm=;

const int maxd=;

int fa[maxn];

int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }

inline bool union_find(int x,int y)

{

    int t1=find(x),t2=find(y);

    if(t1==t2) return false;

    fa[t2]=t1;

    return true;

}

struct Edge

{

    int to,next;

    int val;

}edge[maxm<<];

int head[maxn];

int maxedge;

inline void addedge(int u,int v,int c)

{

    edge[++maxedge]=(Edge){v,head[u],c};

    head[u]=maxedge;

    edge[++maxedge]=(Edge){u,head[v],c};

    head[v]=maxedge;

}

struct Road

{

    int from,to;

    int cost;

    bool operator < (const Road t) const

    {

        return cost>t.cost;

    }

}road[maxm];

int n,m;

inline void init()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++) scanf("%d%d%d",&road[i].from,&road[i].to,&road[i].cost);

    for(int i=;i<=n;i++) fa[i]=i;

    memset(head,-,sizeof(head));

    maxedge=-;

}

void kruskal()

{

    sort(road+,road+m+);

    int pos=,tot=;

    while(pos<=m && tot^(n-))

    {

        if(union_find(road[pos].from,road[pos].to)) tot++,addedge(road[pos].from,road[pos].to,road[pos].cost);

        pos++;

    }

}

int f[maxn][maxd+],dp[maxn][maxd+]; // the node 2^j after u

int depth[maxn];

void dfs(int u,int deep)

{

    depth[u]=deep;

    for(int k=;(<<k)<=n;k++)

    {

        f[u][k] = f[f[u][k-]][k-];

        dp[u][k] = min(dp[u][k-] , dp[f[u][k-]][k-]);

    }

    for(int i=head[u];~i;i=edge[i].next)

    {

        int v=edge[i].to;

        if(!depth[v])

        {

            f[v][]=u;dp[v][]=edge[i].val;//initialize here rather than in the former context!! no considering the roor coz INF is INF, not changing and not visiting the value!!

            dfs(v,deep+);

        }

    }

}

int Find(int u,int v)

{

    int ans=INF;

    if(depth[u] < depth[v]) swap(u,v);// making the u is deeper!!

    // make u v at the same depth

    for(int k=maxd;k>=;k--) // k>=0 here!! or cannot jump at the same depth!!!

        if(depth[v] <= depth[f[u][k]]) // f[0] = 0, indicates its beyond the root!!

        {

            smin( ans , dp[u][k] );

            u=f[u][k];

        }

    if(u == v) return ans; //special judge of one of them is the LCA

    // jump at the same time

    for(int k=maxd;k>=;k--) // k>=0 here too!!

        if(f[u][k] ^ f[v][k])

        {

            smin(ans , min( dp[u][k] , dp[v][k] ) );

            u = f[u][k];

            v = f[v][k];

        }

    return min( ans , min(dp[u][] , dp[v][])); // u v this time is the F1 of LCA

}

int main()

{

    freopen("truck.in","r",stdin);

    freopen("truck.out","w",stdout);

    init();

    kruskal();

    memset(dp,0x3f,sizeof(dp));

    for(int i=;i<=n;i++)

        if(!depth[i]) dfs(i,);

    int q;

    scanf("%d",&q);

    while(q--)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        if(find(x)^find(y)) printf("-1\n");

        else printf("%d\n",Find(x,y));

    }

    return ;

}

然后的话粘一发 LCA 裸题 HDU 2874

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<vector>

#include<queue>

#include<stack>

#include<map>

#include<set>

#include<string>

#include<iomanip>

#include<ctime>

#include<climits>

#include<cctype>

#include<algorithm>

#ifdef WIN32

#define AUTO "%I64d"

#else

#define AUTO "%lld"

#endif

using namespace std;

const int maxn=;

struct Edge

{

    int to,next;

    int val;

}edge[maxn*maxn];

int head[maxn];

int maxedge;

inline void addedge(int u,int v,int c)

{

    edge[++maxedge]=(Edge){v,head[u],c};

    head[u]=maxedge;

    edge[++maxedge]=(Edge){u,head[v],c};

    head[v]=maxedge;

}

int n,m,q;

int fa[maxn];

int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }

bool union_find(int x,int y)

{

    int t1=find(x),t2=find(y);

    if(t1==t2) return false;

    fa[t2]=t1;

    return true;

}

int maxnode;

int dfn[maxn],ver[maxn<<];//dfn: first visit maxnode, ver: reverse function of dfn, indicating the number of vertex

int depth[maxn<<],dis[maxn];//depth: the depth of dfn, dis: from root to vertex

inline bool init()

{

    if(!~scanf("%d%d%d",&n,&m,&q)) return false;

    for(int i=;i<=n;i++) fa[i]=i;

    memset(head,-,sizeof(head));

    memset(dfn,,sizeof(dfn));

    maxedge=-;maxnode=;

    for(int i=;i<=m;i++)

    {

        int u,v,c;

        scanf("%d%d%d",&u,&v,&c);

        addedge(u,v,c);

        union_find(u,v);

    }

    return true;

}

void dfs(int u,int deep)

{

    dfn[u]=++maxnode;ver[maxnode]=u;depth[maxnode]=deep;

    for(int i=head[u];~i;i=edge[i].next)

    {

        int v=edge[i].to;

        if(dfn[v]) continue;

        dis[v]=dis[u]+edge[i].val;

        dfs(v,deep+);

        depth[++maxnode]=deep;ver[maxnode]=u;

    }

}

const int maxdepth=;

int dp[maxn<<][maxdepth];

void ST(int n)// n=::maxnode

{

    for(int i=;i<=n;i++) dp[i][]=i;

    for(int j=;(<<j)<=n;j++)//careful of the limits

        for(int i=;i+(<<j)-<=n;i++)//careful of the limits by y=dp[i+(1<<j-1)][j-1] and the limit of i+(1<<j)-1<=n, must -1 'coz the i+(1<<j)-1 is possible to be n!!

        {

            int x=dp[i][j-],y=dp[i+(<<j-)][j-];

            dp[i][j]=depth[x]<depth[y]?x:y;

        }

}

inline int RMQ(int l,int r)

{

    int k=;

    while(<<(k+)<=r-l+) k++;// careful of the limits!!

    int x=dp[l][k],y=dp[r-(<<k)+][k];

    return depth[x]<depth[y]?x:y;

}

inline int LCA(int u,int v)

{

    int x=dfn[u],y=dfn[v];

    if(x>y) swap(x,y);

    int root=RMQ(x,y);

    return ver[root];

}

int main()

{

    freopen("city.in","r",stdin);

    freopen("city.out","w",stdout);

    while(init())

    {

        for(int i=;i<=n;i++)

            if(!dfn[i]) dfs(i,);

        ST(maxnode);

        while(q--)

        {

            int x,y;

            scanf("%d%d",&x,&y);

            if(find(x)^find(y)) printf("Not connected\n");

            else printf("%d\n",dis[x]+dis[y]-(dis[LCA(x,y)]<<));

        }

    }

    return ;

}

最新文章

  1. [LeetCode] Moving Average from Data Stream 从数据流中移动平均值
  2. 谢欣伦 - OpenDev原创教程 - 蓝牙设备查找类CxBthRadio &amp; CxBthRadioFind
  3. WebUploader UEditor chrome 点击上传文件选择框会延迟几秒才会显示 反应很慢
  4. js正则,电话，邮箱
  5. C＃读取XML文件的方法
  6. POJ1459Power Network（dinic模板）
  7. sql2008读取excel
  8. 空格的URL编码
  9. ALTER---删除字段
  10. EasyUI 树形菜单tree 定义图标
  11. ADO.Net连接模式
  12. 使用Row_Number()分页优化
  13. u盘烧写后实际容量变小了
  14. SQL知识目录
  15. ABP架构学习系列一 整体项目结构及目录
  16. C++标准模板库（STL）介绍：set的基本用法
  17. leetcode-79-单词搜索（用dfs解决）
  18. C# WPF 粘贴板记录器
  19. CSS3-盒模型-resize属性
  20. TButton.Repaint的执行过程

热门文章

  1. 【Stage3D学习笔记续】山寨Starling（二）：VertexData探幽
  2. C#利用API制作类似QQ一样的右下角弹出窗体
  3. ef6 dbfirst 实现同一套代码多个数据库访问
  4. 2015北京网络赛 A题 The Cats&#39; Feeding Spots 暴力
  5. 使用android x86进行android应用开发.
  6. 给定表达式[x/2] + y + x * y, 其中x,y都是正整数。
  7. .NET实现单点登录研究过程总结--【SSO】
  8. android128 zhihuibeijing 科大讯飞 语音识别
  9. android的界面编程
  10. extremeComponents（ec）源码分析