题解

48 条题解

  • 4
    @ 2016-10-23 22:47:02

    其实很简单。
    先克鲁斯卡尔求最大生成树(生成出来的无根树要转为有根树)
    其次输入X和Y,求X和Y的LCA(最近公共祖先)(这里如果并查集的祖先不同可以直接输出-1)
    求LCA有很快的倍增算法,但是在这个地方其实不需要。窝就是先从X遍历到X的根节点,遍历的时候每遍历一个点就记录下来(这里一定要注意两端的点,即X和X的根节点,一定要标记,我被这个坑了好久)。再从Y向根节点遍历,一直遍历到某个已经标记过的点(在从X遍历到X的根节点时做的标记~),遍历的时候ans=min(ans,正在遍历的边的权值)(ans一开始设置为一个很大的数,如100000000),就是ans为所有从Y向根节点遍历所经过的边的权值中的最小值。然后遍历到某个标记过的点时,那个点就是我们要求的LCA,然后再从X向LCA遍历,遍历的时候依然是:ans=min(ans,正在遍历的边的权值),然后输出ans

    36行的C++AC代码:

    #include <bits/stdc++.h>
    using namespace std;
    int n,m,q,x,y,ans,f[10005],pre[10005],cost[10005],cnt;bool book[10005];
    int findf(int x){return f[x]==x?x:(f[x]=findf(f[x]));}
    struct edge{int x,y,z;}ne;
    bool edcmp(edge e1,edge e2){return e1.z>e2.z;}
    vector<edge> eds;vector<pair<int,int> > tree[10005];
    void build_tree(int u){for(vector<pair<int,int> >::iterator i=tree[u].begin();i!=tree[u].end();i++)if(!pre[i->first])pre[i->first]=u,cost[i->first]=i->second,build_tree(i->first);}
    int main()
    {
        ios::sync_with_stdio(0); 
        cin>>n>>m;
        for(int i=1;i<=n;i++)f[i]=i;
        for(int i=1;i<=m;i++)cin>>ne.x>>ne.y>>ne.z,eds.push_back(ne);
        sort(eds.begin(),eds.end(),edcmp);
        for(vector<edge>::iterator i=eds.begin();cnt<n-1&&i!=eds.end();i++)
        {
            int fa[2]={findf(i->x),findf(i->y)}; 
            if(fa[0]!=fa[1])cnt++,tree[i->x].push_back(make_pair(i->y,i->z)),tree[i->y].push_back(make_pair(i->x,i->z)),f[fa[0]]=fa[1];
        }
        for(int i=1;i<=n;i++)if(!pre[i])pre[i]=i,build_tree(i);
        cin>>q;
        while(q--)
        {
            memset(book,0,sizeof(book)),ans=100000000;
            cin>>x>>y;if(findf(x)!=findf(y)){cout<<-1<<endl;continue;}
            int lca,j=x;
            do book[j]=1,j=pre[j];while(pre[j]!=j);
            book[j]=1,j=y;
            while(!book[j])ans=min(ans,cost[j]),j=pre[j];
            lca=j,j=x;
            while(j!=lca)ans=min(ans,cost[j]),j=pre[j];
            cout<<ans<<endl;
        }
        return 0;
    }
    
  • 1
    @ 2018-08-04 16:18:29
    #include<bits/stdc++.h>
    using namespace std;
    
    struct node{
        int x,y,z;
        friend bool operator <(const node& x,const node& y) {
            return x.z>y.z;
        }
    } edge[50005];
    int n,m,Q,f[10005],ans[50005];
    set<int> q[10005];
    
    inline int find(int x) {
        while (x!=f[x]) x=f[x]=f[f[x]];
        return x;
    }
    
    int main() {
        memset(ans,-1,sizeof(ans));
        scanf("%d%d",&n,&m);
        for (int i=0;i<m;i++) scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
        sort(edge,edge+m);
        scanf("%d",&Q);
        for (int i=1;i<=Q;i++) {
            int x,y; scanf("%d%d",&x,&y);
            q[x].insert(i);
            q[y].insert(i);
        }
        for (int i=1;i<=n;i++) f[i]=i; 
        for (int i=0;i<m;i++) {
            int findx=find(edge[i].x),findy=find(edge[i].y);
            if (findx==findy) continue;
            if (q[findx].size()>q[findy].size()) swap(findx,findy);
            for (set<int>::iterator it=q[findx].begin();it!=q[findx].end();it++) {
                int cur=*it;
                if (!q[findy].count(cur)) q[findy].insert(cur);
                else {
                    ans[cur]=edge[i].z;
                    q[findy].erase(cur);
                }
            }
            f[findx]=findy;
        }
        for (int i=1;i<=Q;i++) printf("%d\n",ans[i]);
        return 0;
    }
    
  • 1
    @ 2018-03-18 00:09:11

    先更新边权,再更新倍增点(bug调了五分钟)

    应该是入OI以来写的最长的代码了,比某些BFS/DFS代码还长....

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    using namespace std;
    
    const int INF = 0x3f3f3f3f;
    const int MAXN = 2e4+7;
    const int MAXM = 1e5+7;
    
    int n, m, qy;
    int origfrom[MAXM], origto[MAXM], origl[MAXM], origid[MAXM];
    // adjacent table
    int ecnt;
    int first[MAXN], nxt[MAXN], to[MAXN], l[MAXN];
    // Union find set
    int ufs[MAXN];
    // LCA
    int tlog;
    int f[MAXN][20], fl[MAXN][20];
    int d[MAXN], v[MAXN];
    
    int lcainit(int a){
      queue<int> q;
      d[a] = 1;
      q.push(a);
      while(!q.empty()){
        int x = q.front();
        q.pop();
        if(v[x]) continue;
        // cout << x << " ";
        v[x] = 1;
        for(int e=first[x]; e!=0; e=nxt[e]){
          int y = to[e];
          if(!v[y]){
            d[y] = d[x]+1;
            f[y][0] = x;
            fl[y][0] = l[e];
            for(int i=1; i<=tlog; i++){
              f[y][i] = f[f[y][i-1]][i-1];
              fl[y][i] = min(fl[y][i-1], fl[f[y][i-1]][i-1]);
            }
            q.push(y);
          }
        }
      }
    }
    
    int lca(int a, int b){
      int ans = INF;
      if(d[a] < d[b]) swap(a, b);
      // cout << a << " ";
      for(int i=tlog; i>=0; i--){
        if(d[f[a][i]] >= d[b]){
          // cout << i << " " << fl[a][i] << endl;
          ans = min(ans, fl[a][i]);
          a = f[a][i];
        }
      }
      if(a == b){
        // return a;
        return ans;
      }
      for(int i=tlog; i>=0; i--){
        if(f[a][i] != f[b][i]){
          ans = min(ans, fl[a][i]);
          a = f[a][i];
          ans = min(ans, fl[b][i]);
          b = f[b][i];
        }
      }
      ans = min(ans, fl[a][0]);
      ans = min(ans, fl[b][0]);
      return ans;
      // return f[a][0];
    }
    
    bool cmp(int a, int b){
      return origl[a] > origl[b];
    }
    
    void init(int n){
      for(int i=0; i<=n; i++){
        ufs[i] = i;
      }
      return;
    }
    
    int find(int a){
      int root, ta = a, tta = a;
      while(ta != ufs[ta]){
        ta = ufs[ta];
      }
      root = ta;
      while(ta != ufs[ta]){
        tta = ta;
        ta = ufs[ta];
        ufs[tta] = root;
      }
      return root;
    }
    
    void unite(int a, int b){
      int roota = find(a), rootb = find(b);
      ufs[roota] = rootb;
      return;
    }
    
    bool sameufs(int a, int b){
      return find(a) == find(b);
    }
    
    void add_edge(int tfrom, int tto, int tl){
      ++ecnt;
      nxt[ecnt] = first[tfrom];
      first[tfrom] = ecnt;
      to[ecnt] = tto;
      l[ecnt] = tl;
      return;
    }
    
    int main(){
      // freopen("1967.txt", "r", stdin);
      int tfrom, tto, tl;
      scanf("%d%d", &n, &m);
      tlog = (int) log(n)/log(2) + 1;
      init(n);
      for(int i=0; i<m; i++){
        scanf("%d%d%d", &origfrom[i], &origto[i], &origl[i]);
        origid[i] = i;
      }
      sort(origid, origid+m, cmp);
      for(int i=0; i<m; i++){
        int ti = origid[i];
        if(!sameufs(origfrom[ti], origto[ti])){
          unite(origfrom[ti], origto[ti]);
          // cout << origfrom[ti] << " " << origto[ti] << " " << origl[ti] << endl;
          add_edge(origfrom[ti], origto[ti], origl[ti]);
          add_edge(origto[ti], origfrom[ti], origl[ti]);
        }
      }
      memset(fl, 0x3f, sizeof(fl));
      for(int i=1; i<=n; i++){
        if(!d[i]){
          lcainit(i);
        }
      }
      // for(int i=1; i<=n; i++){
      //   for(int j=0; j<=tlog; j++){
      //     cout << fl[i][j] << " " ;
      //   }
      //   cout << endl;
      // }
      scanf("%d", &qy);
      for(int i=0; i<qy; ++i){
        scanf("%d %d", &tfrom, &tto);
        if(sameufs(tfrom, tto)){
          printf("%d\n", lca(tfrom, tto));
        }else{
          printf("%d\n", -1);
        }
      }
    
      return 0;
    }
    
    

    评测情况

    真的有点慢了

     Accepted
    /in/foo.cc: In function 'int lcainit(int)':
    /in/foo.cc:49:1: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^
    /in/foo.cc: In function 'int main()':
    /in/foo.cc:126:19: warning: unused variable 'tl' [-Wunused-variable]
       int tfrom, tto, tl;
                       ^~
    #   状态  耗时  内存占用
    #1   Accepted   6ms 4.344 MiB
    #2   Accepted   5ms 5.125 MiB
    #3   Accepted   15ms    3.715 MiB
    #4   Accepted   16ms    3.621 MiB
    #5   Accepted   21ms    4.117 MiB
    #6   Accepted   15ms    4.75 MiB
    #7   Accepted   61ms    4.402 MiB
    #8   Accepted   64ms    4.25 MiB
    #9   Accepted   62ms    4.168 MiB
    #10  Accepted   73ms    4.656 MiB
    #11  Accepted   62ms    4.293 MiB
    #12  Accepted   49ms    4.75 MiB
    #13  Accepted   534ms   4.879 MiB
    #14  Accepted   402ms   5.062 MiB
    #15  Accepted   424ms   5.141 MiB
    #16  Accepted   385ms   4.422 MiB
    #17  Accepted   513ms   4.75 MiB
    #18  Accepted   378ms   4.445 MiB
    #19  Accepted   336ms   4.375 MiB
    #20  Accepted   349ms   5.246 MiB
    
  • 1
    @ 2017-11-02 14:50:06

    不用倍增
    暴力lca完全没问题
    各种模板套起来

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int n,m;
    int fa[10010];
    struct edge{
        int q,z,v;
    }a[50010];
    int fi[10010],ne[50010],to[50010],w[50010];
    int father[10010];
    int e=0;
    int deep[10010];
    int road[10010];
    int ans=99999999;
    void build(int x,int y,int z)
    {
        e++;
        to[e]=y;
        w[e]=z;
        ne[e]=fi[x];
        fi[x]=e;
    }
    int cmp(const edge &x,const edge &y)
    {
        return x.v>y.v;
    }
    int find(int x)
    {
        if(x==fa[x]) return x;
        else return fa[x]=find(fa[x]);
    }
    void kel()
    {
        int k=0;
        for(int i=1;i<=m&&k<n;i++)
        {
            if(k==n-1) break;
            if(find(a[i].q)!=find(a[i].z))
            {
                k++;
                fa[find(a[i].q)]=find(a[i].z);                                                          
                build(a[i].q,a[i].z,a[i].v);
                build(a[i].z,a[i].q,a[i].v);
            }
        }
        return;
    }
    
    int dfs(int x,int dep,int root)
    {
        deep[x]=dep;
        for(int i=fi[x];i>0;i=ne[i])
        {
            if(deep[to[i]]!=0||to[i]==root) continue;
            else
            {
                father[to[i]]=x;
                road[to[i]]=w[i];
                dfs(to[i],dep+1,root);
            }
        }
    }
    
    
    int lca(int x,int y)
    {
        if(find(x)!=find(y)) 
        {
            ans=-1;
        }
        else
        {
            ans=99999999;
          while(deep[x]>deep[y]) 
          {
            ans=min(ans,road[x]);
            x=father[x];
          }
          while(deep[x]<deep[y])
          {
            ans=min(ans,road[y]);
            y=father[y];
          } 
          while(x!=y)
          {
            ans=min(ans,road[x]);
            ans=min(ans,road[y]);
            x=father[x];
            y=father[y];
          } 
        }
        return ans;
    }
    int main()
    {
        memset(road,0x3f,sizeof(road));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) 
        {
            fa[i]=i;
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&a[i].q,&a[i].z,&a[i].v);
        }
        sort(a+1,a+m+1,cmp);
        kel();
        for(int i=1;i<=n;i++)
         if(fa[i]==i) 
         {
            father[i]=i;
            dfs(i,0,i);
         }
        int q,x,y;
        scanf("%d",&q);
        int ans;
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d",&x,&y);
            ans=lca(x,y);
            printf("%d\n",ans);
        }
        return 0;
    }
    
  • 0
    @ 2019-01-28 20:36:35

    重点在于把思路理清,思想都在代码里了,请笑纳。
    ```cpp
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #define For(i,l,r) for(int i=l;i<=r;i++)
    #define Dor(i,l,r) for(int i=l;i>=r;i--)
    #define N 10005
    #define M 50005
    #define ll long long
    using namespace std;

    struct node{
    int u,v,val;
    }a[M];

    //核心:求最大生成树,然后利用倍增算法求最值,复杂度O(nlogn)
    int w[N*2],to[N*2],head[N*2],nxt[N*2],cnt=0,f[N];
    int n,m,dep[N],fa[N][25],val[N][25],tlog;
    //添边
    void add(int u,int v,int cost)
    {
    nxt[++cnt]=head[u];
    head[u]=cnt;
    w[cnt]=cost;
    to[cnt]=v;
    }
    //并查集
    int getf(int x){
    if (x==f[x]) return x;
    f[x]=getf(f[x]);
    return f[x];
    }
    void combine(int x,int y){
    x=getf(x);
    y=getf(y);
    f[x]=y;
    }
    bool query(int x,int y){
    x=getf(x);
    y=getf(y);
    return (x==y);
    }
    bool cmp(node a,node b){
    return a.val>b.val;
    }
    //求最大生成树
    void Kruskal(){
    int rest=n-1;
    For(i,1,m){
    if (!rest) break;
    if (!query(a[i].u,a[i].v)){
    combine(a[i].u,a[i].v);
    add(a[i].u,a[i].v,a[i].val);
    add(a[i].v,a[i].u,a[i].val);
    rest--;
    }
    }
    }
    //遍历深度
    void dfs(int t,int f){
    dep[t]=dep[f]+1;fa[t][0]=f;
    for(int i=head[t];i;i=nxt[i]){
    if (to[i]!=f){
    val[to[i]][0]=w[i];
    dfs(to[i],t);
    }
    }

    }
    void init(){
    dfs(1,0);
    For(j,0,tlog){
    For(i,1,n){
    fa[i][j+1]=fa[fa[i][j]][j];
    val[i][j+1]=min(val[i][j],val[fa[i][j]][j]);//存储最值
    }
    }
    }
    //倍增求lca和最值
    int lca(int x,int y){
    int ans=2100000000;
    if (!query(x,y)) return -1;
    if (dep[x]<dep[y]) swap(x,y);
    Dor(j,tlog,0) if (dep[fa[x][j]]>=dep[y]){
    ans=min(ans,val[x][j]);
    x=fa[x][j];
    }
    Dor(j,tlog,0) if (fa[x][j]!=fa[y][j]){
    ans=min(ans,val[x][j]);
    ans=min(ans,val[y][j]);
    x=fa[x][j],y=fa[y][j];
    }
    if (x!=y)
    {
    ans=min(ans,val[x][0]),ans=min(ans,val[y][0]);
    x=fa[x][0],y=fa[y][0];
    }
    return ans;
    }
    int main(){
    memset(val,127/3,sizeof(val));
    scanf("%d%d",&n,&m);
    For(i,1,m){
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    a[i].u=x,a[i].v=y,a[i].val=z;
    }

    For(i,1,n) f[i]=i;
    tlog= (int)log(n)/log(2)+1;
    sort(a+1,a+m+1,cmp);
    Kruskal();
    init();
    int q;
    scanf("%d",&q);
    For(i,1,q){
    int x,y;
    scanf("%d%d",&x,&y);
    printf("%d\n",lca(x,y));
    }
    return 0;
    }
    ```

  • 0
    @ 2018-09-02 15:48:37

    先用Kruskal算法求出最大生成树,然后LCA时求限重最小值。

    #include <cstdio>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    int n, m, q;
    
    int parent[10001];
    int depth[10001];
    
    int ancestor[10001][15];
    int minweight[10001][15];
    
    struct FullRoad {
        int x;
        int y;
        int z;
    };
    
    FullRoad full_roads[50001];
    
    bool cmp(FullRoad a, FullRoad b)
    {
        return a.z > b.z;
    }
    
    struct Road {
        int y;
        int z;
    };
    vector<Road> conn[10001];
    
    int uf[10001];
    
    int uf_find(int a)
    {
        if (uf[a] == a) return a;
        uf[a] = uf_find(uf[a]);
        return uf[a];
    }
    
    void uf_union(int a, int b)
    {
        a = uf_find(a);
        b = uf_find(b);
        uf[a] = b;
    }
    
    void mk_tree(int node, int p, int d, int wt)
    {
        if (parent[node] != 0) return;
        parent[node] = p;
        depth[node] = d;
        minweight[node][0] = wt;
        for (int i = 0; i < conn[node].size(); i++) {
            mk_tree(conn[node][i].y, node, d + 1, conn[node][i].z);
        }
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            uf[i] = i;
        }
        for (int i = 1; i <= m; i++) {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            full_roads[i].x = x;
            full_roads[i].y = y;
            full_roads[i].z = z;
        }
        sort(full_roads + 1, full_roads + m + 1, cmp);
        for (int i = 1; i <= m; i++) {
            int x = full_roads[i].x;
            int y = full_roads[i].y;
            int z = full_roads[i].z;
            if (uf_find(x) != uf_find(y)) {
                uf_union(x, y);
                Road r;
                r.y = y;
                r.z = z;
                conn[x].push_back(r);
                r.y = x;
                conn[y].push_back(r);
            }
        }
        for (int i = 1; i <= n; i++) {
            mk_tree(i, -1, 0, -1);
            ancestor[i][0] = parent[i];
        }
        for (int i = 1; i <= 14; i++) {
            for (int j = 1; j <= n; j++) {
                ancestor[j][i] = ancestor[j][i-1];
                if (ancestor[j][i] != -1) ancestor[j][i] = ancestor[ancestor[j][i-1]][i-1];
                minweight[j][i] = min(minweight[j][i-1], minweight[ancestor[j][i-1]][i-1]);
            }
        }
        scanf("%d", &q);
        for (int i = 1; i <= q; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            int ans = 2000000000;
            if (uf_find(x) != uf_find(y)) {
                printf("-1\n");
                continue;
            }
            if (depth[x] > depth[y]) {
                int t = x;
                x = y;
                y = t;
            }
            for (int i = 0; i <= 14; i++) {
                if ((depth[y] - depth[x]) & (1 << i)) {
                    ans = min(ans, minweight[y][i]);
                    y = ancestor[y][i];
                }
            }
            if (x == y) {
                printf("%d\n", ans);
                continue;
            }
            for (int i = 14; i >= 0; i--) {
                if (ancestor[x][i] != ancestor[y][i]) {
                    ans = min(ans, minweight[x][i]);
                    ans = min(ans, minweight[y][i]);
                    x = ancestor[x][i];
                    y = ancestor[y][i];
                }
            }
            ans = min(ans, minweight[x][0]);
            ans = min(ans, minweight[y][0]);
            printf("%d\n", ans);
        }
        return 0;
    }
    
  • 0
    @ 2017-10-22 23:48:48

    先用kruskal求最大生成树
    再对每次询问在最大生成树上求他们到lca路径中的最小边权。倍增求lca,注意先更新最小边权再更新x和y(被这个坑了2个小时。。)
    AC代码

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #include<vector>
    using namespace std;
    typedef long long ll;
    const int maxn=1e4+10;
    const int inf=0x3f3f3f3f;
    struct edge{
        int from,nxt,to,w;
    }e[maxn*20],ed[maxn*10];
    int last[maxn],cnt,n,m,dep[maxn],f[maxn][25],c[maxn][25],fa[maxn];
    vector<int> Set_of_edge;
    inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
    inline int read()
    {
        int x=0,f=1;char c=getchar();
        while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
        while(isdigit(c)){x=x*10+c-'0';c=getchar();}
        return x*f;
    }
    inline void insert(int u,int v,int c)
    {
        e[++cnt]=(edge){u,last[u],v,c};last[u]=cnt;
        e[++cnt]=(edge){v,last[v],u,c};last[v]=cnt;
    }
    inline void dfs(int cur,int pre)
    {
        f[cur][0]=pre,dep[cur]=dep[pre]+1;
        for(register int i=1;i<=20;i++)
        {
            f[cur][i]=f[f[cur][i-1]][i-1];
            c[cur][i]=min(c[f[cur][i-1]][i-1],c[cur][i-1]);
        }
        for(register int i=last[cur];i;i=e[i].nxt)
        {
            register int v=e[i].to;
            if(v==pre) continue;
            c[v][0]=e[i].w;
            dfs(v,cur);
        }
    }
    inline int lca(int x,int y)
    {
        int ret=inf;
        if(x==y) return 0;
        if(dep[x]<dep[y])swap(x,y);
        for(register int i=20;i>=0;i--)
        {
            if((dep[x]-dep[y])>=(1<<i)) ret=min(ret,c[x][i]),x=f[x][i];
        }
        if(x==y) return ret;
        for(register int i=20;i>=0;i--)
        {
            if(f[x][i]!=f[y][i])
            {
                ret=min(min(c[x][i],c[y][i]),ret);
                x=f[x][i],y=f[y][i];
            }
        }
        if(x==y) return ret;
        return min(min(c[x][0],c[y][0]),ret);
    }
    inline bool comp(const edge &a,const edge &b)
    {
        return a.w>b.w;
    }
    int main()
    {
        n=read(),m=read();
        for(int i=1;i<=m;i++)
        {
            int u=read(),v=read(),c=read();
            ed[i].from=u,ed[i].to=v,ed[i].w=c;
        }
        sort(ed+1,ed+1+m,comp);
        for(int i=1;i<=n;i++) fa[i]=i;
        for(register int i=1;i<=m;i++)
        {
            int fx=find(ed[i].from),fy=find(ed[i].to);
            if(fx==fy) continue;
            Set_of_edge.push_back(i),fa[fx]=fy;
        }
        for(register int i=0;i<Set_of_edge.size();i++)
            insert(ed[Set_of_edge[i]].from,ed[Set_of_edge[i]].to,ed[Set_of_edge[i]].w);
        dep[1]=1;
        dfs(1,0);
        int q=read();
        while(q--)
        {
            int s=read(),t=read();
            if(find(s)!=find(t)){puts("-1");continue;}
            printf("%d\n",lca(s,t));
        }
        return 0;
    }
    
    
  • 0
    @ 2016-09-06 10:04:51

    // 最大生成树 lca 时维护min_len.

    uses math;
    type
        re=record
            v,len,next:longint;
        end;
        rea=record
            u,v,len:longint;
        end;
    
    var
        n,m,q,u,v,z,i,tot,x,y,max_deep,ans:longint;
        father,deep,last:array[0..10000]of longint;
        flag:array[0..10000]of boolean;
        f,min_len:array[0..10000,0..14]of longint;
        g:array[0..50000]of rea;
        t:array[0..10000*2]of re;
    
    procedure add(u,v,z:longint);
    begin
        inc(tot);
        t[tot].v:=v;
        t[tot].len:=z;
        t[tot].next:=last[u];
        last[u]:=tot;
    end;
    
    function find(i:longint):longint;
    begin
        if father[i]=i then exit(i);
        father[i]:=find(father[i]);
        exit(father[i]);
    end;
    
    procedure sort(l,r:longint);
    var
        i,j,x:longint;
        y:rea;
    begin
        i:=l; j:=r;
        x:=g[(l+r) div 2].len;
        repeat
            while g[i].len>x do inc(i);
            while x>g[j].len do dec(j);
            if not(i>j) then
            begin
                y:=g[i]; g[i]:=g[j]; g[j]:=y;
                inc(i); j:=j-1;
            end;
        until i>j;
        if l<j then sort(l,j);
        if i<r then sort(i,r);
    end;
    
    procedure Kruskal;
    var
        i,j,x,y:longint;
    begin
        sort(1,m);
        for i:=1 to n do father[i]:=i;
        for i:=1 to m do
        begin
            x:=find(g[i].u); y:=find(g[i].v);
            if x<>y then
                    begin
                            father[x]:=y;
                            add(g[i].u,g[i].v,g[i].len); add(g[i].v,g[i].u,g[i].len);
                    end;
        end;
    end;
    
    procedure Dfs_t(i,fat:longint);
    var
        x,tox:longint;
    begin
            x:=last[i];
        while x<>0 do
        begin
            tox:=t[x].v;
                    if tox<>fat then
                    begin
                    flag[tox]:=true;
                        deep[tox]:=deep[i]+1;
                    max_deep:=max(max_deep,deep[tox]);
                    f[tox][0]:=i;
                    min_len[tox][0]:=t[x].len;
                            Dfs_t(tox,i);
                    end;
            x:=t[x].next;
        end;
    end;
    
    procedure Init_f;
    var
        i,j:longint;
    begin
        for j:=1 to trunc(ln(max_deep)/ln(2)) do
            for i:=1 to n do
                if deep[i]<<j>=1 then
                begin
                    f[i][j]:=f[f[i][j-1]][j-1];
                    min_len[i][j]:=min(min_len[i][j-1],min_len[f[i][j-1]][j-1]);
                end;
    end;
    
    procedure Init;
    var
        i,j:longint;
    begin
        readln(n,m);
        for i:=1 to m do readln(g[i].u,g[i].v,g[i].len);
        Kruskal;
        for i:=1 to n do
            if not flag[i] then Dfs_t(i,0);
        Init_f;
    end;
    
    procedure swap(var x,y:longint);
    var
            cmp:longint;
    begin
            cmp:=x; x:=y; y:=cmp;
    end;
    
    function lca(x,y:longint):longint;
    var
        k,p:longint;
    begin
        if deep[x]<deep[y] then swap(x,y);
        p:=deep[x]-deep[y]; k:=0;
        while p<>0 do
        begin
            if (p and 1=1) then
            begin
                            ans:=min(ans,min_len[x][k]);
                x:=f[x][k];
            end;
            inc(k);
            p:=p>>1;
        end;
        if x=y then exit;
        k:=0;
        while k>=0 do
        begin
            if f[x][k]<>f[y][k] then
            begin
                ans:=min(ans,min_len[x][k]);
                ans:=min(ans,min_len[y][k]);
                x:=f[x][k];
                y:=f[y][k];
                inc(k);
            end else dec(k);
        end;
        ans:=min(ans,min_len[x][0]);
            ans:=min(ans,min_len[y][0]);
    end;
    
    begin
        Init;
        read(q);
        for i:=1 to q do
        begin
            readln(u,v);
            x:=find(u); y:=find(v);
            if x<>y then writeln(-1) else
            begin
                ans:=maxlongint;
                lca(u,v);
                writeln(ans);
                    end;
        end;
    end.
    
    
  • 0
    @ 2016-07-25 01:53:23

    我加了一个超级根,就是从编号为0的超级根向其他所有点连一个权为-1的路,再做最大生成树
    然后我就一直wa,wa了4个小时
    最后我发现,保存边的数组大小不应该是50000,因为我还引进了好多-1的边,应该开60000(= 10000 + 50000)的数组
    我的青春啊!!!!就这么浪费了!!!

  • 0
    @ 2016-07-15 12:00:59

    测试数据 #0: Accepted, time = 15 ms, mem = 5968 KiB, score = 5

    测试数据 #1: Accepted, time = 0 ms, mem = 5972 KiB, score = 5

    测试数据 #2: Accepted, time = 15 ms, mem = 5968 KiB, score = 5

    测试数据 #3: Accepted, time = 0 ms, mem = 5972 KiB, score = 5

    测试数据 #4: Accepted, time = 15 ms, mem = 5968 KiB, score = 5

    测试数据 #5: Accepted, time = 0 ms, mem = 5968 KiB, score = 5

    测试数据 #6: Accepted, time = 46 ms, mem = 5968 KiB, score = 5

    测试数据 #7: Accepted, time = 62 ms, mem = 5968 KiB, score = 5

    测试数据 #8: Accepted, time = 62 ms, mem = 5972 KiB, score = 5

    测试数据 #9: Accepted, time = 46 ms, mem = 5964 KiB, score = 5

    测试数据 #10: Accepted, time = 78 ms, mem = 5972 KiB, score = 5

    测试数据 #11: Accepted, time = 46 ms, mem = 5968 KiB, score = 5

    测试数据 #12: Accepted, time = 78 ms, mem = 5972 KiB, score = 5

    测试数据 #13: Accepted, time = 78 ms, mem = 5968 KiB, score = 5

    测试数据 #14: Accepted, time = 109 ms, mem = 5968 KiB, score = 5

    测试数据 #15: Accepted, time = 93 ms, mem = 5972 KiB, score = 5

    测试数据 #16: Accepted, time = 93 ms, mem = 5968 KiB, score = 5

    测试数据 #17: Accepted, time = 62 ms, mem = 5972 KiB, score = 5

    测试数据 #18: Accepted, time = 78 ms, mem = 5968 KiB, score = 5

    测试数据 #19: Accepted, time = 78 ms, mem = 5968 KiB, score = 5

    Accepted, time = 1054 ms, mem = 5972 KiB, score = 100
    #include <iostream>
    #include <stdio.h>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    struct SortNode{
    int x,y,cap;
    };
    struct Edge{
    int to,next,cap;
    };
    int min(int x,int y){
    if(x>=y) return y;
    return x;
    }
    Edge edges[100000];
    int cnt;
    int pos[10050];
    int depth[10050];
    int fa[10050];
    int father[10050][32];
    int d[10050][32];
    int root,maxdepth;
    int n,m;
    int dfs_flag[10000];
    SortNode s[100000];
    int MST[100000];
    void addedge(int x,int y,int cap){
    cnt++;
    edges[cnt].to=y;
    if(pos[x]!=0)
    edges[cnt].next=edges[pos[x]].next;
    edges[pos[x]].next=cnt;
    edges[cnt].cap=cap;
    if(pos[x]==0)
    pos[x]=cnt;
    }
    int cmp(const SortNode& a,const SortNode& b){
    return a.cap>b.cap;
    }
    void dfs(int v,int dep){
    if(dep>maxdepth)
    maxdepth=dep;
    dfs_flag[v]=1;
    int x=pos[v];
    depth[v]=dep;
    while(x>0){
    if(!dfs_flag[edges[x].to]){
    dfs(edges[x].to,dep+1);
    father[edges[x].to][0]=v;
    d[edges[x].to][0]=edges[x].cap;
    }
    x=edges[x].next;
    }
    }
    void init(){
    int log=0;
    for(;(1<<log)<maxdepth;log++);
    for(int j=1;j<=log;j++){
    for(int i=1;i<=m;i++){
    if(depth[i]>=(1<<j)){
    father[i][j]=father[father[i][j-1]][j-1];
    d[i][j]=min(d[i][j-1],d[father[i][j-1]][j-1]);
    }
    }
    }
    }
    int jump_to(int x,int dep,int &mincap){
    int p=depth[x]-dep;
    for(int j=0;(1<<j)<=p;j++){
    if((1<<j)&p){
    mincap=min(mincap,d[x][j]);
    x=father[x][j];
    }
    }
    return x;
    }
    int getfather(int x){
    if(fa[x]==x){
    return x;
    }
    fa[x]=getfather(fa[x]);
    return fa[x];
    }
    int get(int x,int y){
    if(getfather(x)!=getfather(y))
    return -1;
    int mincap=2100000000;
    if(depth[x]>depth[y])

    x=jump_to(x,depth[y],mincap);
    else
    y=jump_to(y,depth[x],mincap);
    if(x==y) return mincap;
    int j=0;
    while(father[x][0]!=father[y][0]){
    j=0;
    for(;depth[x]>=(1<<j);j++){
    if(father[x][j+1]==father[y][j+1])
    break;
    }
    mincap=min(mincap,d[x][j]);
    mincap=min(mincap,d[y][j]);
    x=father[x][j];y=father[y][j];

    }
    mincap=min(mincap,d[x][0]);
    mincap=min(mincap,d[y][0]);
    return mincap;
    }
    int main(int argc, char** argv) {
    //freopen("lca.in","r",stdin);
    //freopen("lca.out","w",stdout);
    cnt=0;
    memset(edges,0,sizeof(edges));
    memset(depth,0,sizeof(depth));
    memset(father,0,sizeof(father));
    memset(pos,0,sizeof(pos));
    memset(dfs_flag,0,sizeof(dfs_flag));
    memset(s,0,sizeof(s));
    memset(MST,0,sizeof(MST));
    memset(d,127,sizeof(d));
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
    {
    fa[i]=i;
    }
    cnt=0;
    for(int i=1;i<=n;i++){
    int x,y,cap;
    scanf("%d%d%d",&x,&y,&cap);
    cnt++;
    s[cnt].x=x;
    s[cnt].y=y;
    s[cnt].cap=cap;
    }
    sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++){
    int x=getfather(s[i].x);
    int y=getfather(s[i].y);
    if(x!=y){
    MST[i]=1;
    fa[x]=y;
    }
    }
    cnt=0;
    for(int i=1;i<=n;i++){
    if(MST[i]){
    addedge(s[i].y,s[i].x,s[i].cap);
    addedge(s[i].x,s[i].y,s[i].cap);
    }
    }
    for(int i=1;i<=m;i++){
    if(!dfs_flag[i])
    dfs(i,0);
    }
    init();

    int q;
    scanf("%d",&q);
    int x,y;
    for(int i=1;i<=q;i++){
    scanf("%d%d",&x,&y);
    printf("%d\n",get(x,y));
    }
    return 0;
    }

  • 0
    @ 2016-01-09 20:58:53

    太tm容易错了
    6次RE

    #include <iostream>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #include <cstdio>
    #include <cstdlib>
    using namespace std;
    const int N=100000+100;
    const int M=100000+100;
    int fa[N][21];
    int deep[N],flag[N],flag1[N];
    int p[N],w[N],father[N];
    int b[N],a[N],_next[N];
    int d[N][21];
    int n,m,tcase,root,nn;

    struct node
    {
    int l,r,w;
    }q[M];

    void add(int x,int y,int z)
    {
    nn++;
    a[nn]=x;
    b[nn]=y;
    w[nn]=z;
    _next[nn]=p[x];
    p[x]=nn;
    nn++;
    a[nn]=y;
    b[nn]=x;
    w[nn]=z;
    _next[nn]=p[y];
    p[y]=nn;
    }

    void dfs(int x,int height)
    {
    flag[x]=1;
    for(int i=1;i<=20;i++)
    {
    if(deep[x]<(1<<i)) break;
    fa[x][i]=fa[fa[x][i-1]][i-1];
    d[x][i]=min(d[x][i-1],d[fa[x][i-1]][i-1]);
    }
    int e=p[x];
    while(e>0)
    {
    int k=b[e];
    if(!flag[k])
    {
    deep[k]=deep[x]+1;
    fa[k][0]=x;
    d[k][0]=w[e];
    dfs(k,height+1);
    }
    e=_next[e];
    }
    }

    int ask(int x,int y)
    {
    if(deep[x]<deep[y]) swap(x,y);
    int t=deep[x]-deep[y];
    for(int i=20;i>=0;i--)
    {
    if((1<<i)&t)
    x=fa[x][i];
    }
    for(int i=20;i>=0;i--)
    if(fa[x][i]!=fa[y][i])
    {
    x=fa[x][i];
    y=fa[y][i];
    }

    if(x==y) return x;
    return fa[x][0];
    }

    int query(int x,int f)
    {
    int minv=1<<29;
    int t=deep[x]-deep[f];
    for(int i=20;i>=0;i--)
    {
    if(t&(1<<i))
    {
    minv=min(minv,d[x][i]);
    x=fa[x][i];
    }
    }
    return minv;
    }

    int findf(int x)
    {
    if(father[x]==x) return x;
    father[x]=findf(father[x]);
    return father[x];
    }

    int merget(int x,int y)
    {
    x=findf(x);
    y=findf(y);
    father[x]=y;
    }

    int cmp(node x,node y)
    {
    return x.w>y.w;
    }

    void init()
    {
    int num=0;
    sort(q+1,q+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
    int fx=findf(q[i].l),fy=findf(q[i].r);
    if(fy!=fx)
    {
    add(q[i].l,q[i].r,q[i].w);
    add(q[i].r,q[i].l,q[i].w);
    father[fx]=fy;
    num++;
    if(num==n-1) break;
    }
    }
    }

    int main()
    {
    memset(d,127/3,sizeof(d));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
    father[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
    scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].w);
    }
    init();
    int p;
    scanf("%d",&p);
    for(int i=1;i<=p;i++)
    {
    int x,y;
    scanf("%d%d",&x,&y);
    if(findf(x)!=findf(y))
    {
    cout<<-1<<endl; continue;
    }
    else
    {
    for(int i=1;i<=n;i++) if(!flag[i]) dfs(i,1);
    int t=ask(x,y);
    int xx=query(x,t);
    int yy=query(y,t);
    printf("%d\n",min(xx,yy));
    }
    }
    return 0;
    }

  • 0
    @ 2015-10-25 14:21:41

    用LCA+最大生成树就AC了,提交了一次就AC了,稀里糊涂就AC了,刚刚还在犯困
    程序186行
    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <string.h>
    #include <functional>
    using namespace std;
    //此题目先求最大生成树然后计算LCA即可
    #define MAXNUM 20000
    #define MAXEDGE 60000
    #define MAXLIMIT 20
    typedef struct EDGE{
    int x;
    int y;
    int w;
    }EDGE;
    class UnionSet{
    private:
    int dat[MAXNUM];
    public:
    void Init(int n)
    {
    int i;
    for (i = 1; i <= n; i++)
    {
    dat[i] = i;
    }
    }
    int Find(int x)
    {
    if (dat[x] == x)
    {
    return x;
    }
    return dat[x] = Find(dat[x]);
    }
    void Union(int x, int y)
    {
    dat[Find(x)] = Find(y);
    }
    };
    EDGE edge[MAXEDGE];
    vector<EDGE> point[MAXNUM];
    int dis[MAXNUM];
    int p[MAXNUM][MAXLIMIT + 1];
    int w[MAXNUM][MAXLIMIT + 1];
    bool v[MAXNUM];
    queue<int> curpoint;
    queue<int> disq;
    UnionSet s;
    int n, m;
    bool cmp(const EDGE &x, const EDGE &y)
    {
    return x.w > y.w;
    }
    void kruskal()
    {
    int i;
    sort(edge, edge + m, cmp);
    s.Init(n);
    for (i = 0; i < m; i++)
    {
    if (s.Find(edge[i].x) != s.Find(edge[i].y))
    {
    s.Union(edge[i].x, edge[i].y);
    point[edge[i].x].push_back(edge[i]);
    swap(edge[i].x, edge[i].y);
    point[edge[i].x].push_back(edge[i]);
    }
    }
    }
    void lca_init()
    {
    int cur;
    int i, j;
    curpoint.push(1);
    dis[1] = 0;
    v[1] = false;
    while (!curpoint.empty())
    {
    cur = curpoint.front();
    curpoint.pop();
    for (i = 0; i < point[cur].size(); i++)
    {
    if (v[point[cur][i].y])
    {
    v[point[cur][i].y] = false;
    dis[point[cur][i].y] = dis[cur] + 1;
    p[point[cur][i].y][0] = cur;
    w[point[cur][i].y][0] = point[cur][i].w;
    curpoint.push(point[cur][i].y);
    }
    }
    }
    for (j = 1; j <= MAXLIMIT; j++)
    {
    for (i = 1; i <= n; i++)
    {
    p[i][j] = p[p[i][j - 1]][j - 1];
    w[i][j] = min(w[i][j - 1], w[p[i][j - 1]][j - 1]);
    }
    }
    }
    int lca(int x, int y)
    {
    int i;
    int wx;
    int wy;
    wx = 1000000000;
    wy = 1000000000;
    if (dis[x] < dis[y])
    {
    swap(x, y);
    }
    if (dis[x]>dis[y])
    {
    for (i = MAXLIMIT; i >= 0; i--)
    {
    if (dis[p[x][i]] > dis[y])
    {
    wx = min(wx, w[x][i]);
    x = p[x][i];
    }
    }
    wx = min(wx, w[x][0]);
    x = p[x][0];
    }
    if (x != y)
    {
    for (i = MAXLIMIT; i >= 0; i--)
    {
    if (p[x][i] != p[y][i])
    {
    wx = min(wx, w[x][i]);
    x = p[x][i];
    wy = min(wy, w[y][i]);
    y = p[y][i];
    }
    }
    wx = min(wx, w[x][0]);
    x = p[x][0];
    wy = min(wy, w[y][0]);
    y = p[y][0];
    }
    return min(wx , wy);
    }
    int main()
    {
    int i, j;
    int x, y, w;
    int cur;
    int q;
    memset(dis, 0, sizeof(dis));
    memset(p, 0, sizeof(p));
    memset(v, true, sizeof(v));
    scanf("%d%d", &n, &m);
    for (i = 0; i < m; i++)
    {
    scanf("%d%d%d", &x, &y, &w);
    if (x>y)
    {
    swap(x, y);
    }
    edge[i].x = x;
    edge[i].y = y;
    edge[i].w = w;
    }
    kruskal();
    lca_init();
    scanf("%d", &q);
    for (i = 0; i < q; i++)
    {
    scanf("%d%d", &x, &y);
    if (s.Find(x) != s.Find(y))
    {
    printf("-1\n");
    }
    else
    {
    printf("%d\n", lca(x, y));
    }
    }
    return 0;
    }

  • 0
    @ 2015-10-24 11:19:03

    写LCA先处理w , 再处理父节点 , 不知为此WA了多少次
    ( 其实一调试就看出来了 , 本人比较懒。。。 )

    /*

    Author : Slience_K
    Belong : C++
    Pro : NOIP 2013 - 1 - 3

    */
    #include <cstdio>
    #include <vector>
    #include <algorithm>
    #define sz 10005
    using namespace std;
    struct Node{
    int u , v , w;
    bool operator < ( const Node & x ) const {
    return w > x.w;
    }
    }data[ 5 * sz ];
    const int INF = ( int )( 1e9 );
    struct Tyep{
    int v , w;
    }dot;
    vector <Tyep> map[ sz ];
    int n , m , q , u , v , f[ sz ] , father[ sz ][ 20 ] , k , power[ 20 ] , w[ sz ][ 20 ] , deep[ sz ];
    int Find( int x ){
    int t , tt;
    t = x;
    while( t != f[ t ] ) t = f[ t ];
    while( x != f[ x ] ){
    tt = f[ x ];
    f[ x ] = t;
    x = tt;
    }
    return t;
    }
    void Dfs( int x , int last , int weight , int d ){
    father[ x ][ 0 ] = last;
    w[ x ][ 0 ] = weight;
    deep[ x ] = d;
    for( int i = 0 ; i < map[ x ].size() ; i++ ){
    v = map[ x ][ i ].v;
    if ( v != last )
    Dfs( v , x , map[ x ][ i ].w , d + 1 );
    }
    }
    void Work(){
    for( int j = 1 ; j <= k ; j++ )
    for( int i = 1 ; i <= n ; i++ ){
    v = father[ i ][ j - 1 ];
    father[ i ][ j ] = father[ v ][ j - 1 ];
    w[ i ][ j ] = min( w[ i ][ j - 1 ] , w[ v ][ j - 1 ] );
    }
    }
    void swap( int &u , int &v ){
    int temp = u;
    u = v;
    v = temp;
    }
    int LCA( int u , int v ){
    int ans = INF;
    while( deep[ u ] > deep[ v ] ) swap( u , v );
    for( int i = k ; i >= 0 ; i-- )
    if ( power[ i ] <= deep[ v ] - deep[ u ] ){
    ans = min( w[ v ][ i ] , ans );
    v = father[ v ][ i ];
    }
    for( int i = k ; i >= 0 ; i-- )
    if ( father[ v ][ i ] != father[ u ][ i ] ){
    ans = min( ans , min( w[ u ][ i ] , w[ v ][ i ] ) );
    u = father[ u ][ i ];
    v = father[ v ][ i ];
    }
    if ( u != v ){
    ans = min( ans , min( w[ u ][ 0 ] , w[ v ][ 0 ] ) );
    }
    return ans;
    }
    int main(){
    freopen( "truck.in" , "r" , stdin );
    freopen( "truck.out" , "w" , stdout );
    scanf( "%d%d" , &n , &m );
    power[ 0 ] = 1;
    k = 0;
    while( power[ k ] <= n ){
    power[ k + 1 ] = power[ k ] * 2;
    k++;
    }
    for( int i = 1 ; i <= m ; i++ )
    scanf( "%d%d%d" , &data[ i ].u , &data[ i ].v , &data[ i ].w );
    sort( data + 1 , data + m + 1 );
    for( int i = 1 ; i <= n ; i++ )
    f[ i ] = i;
    for( int i = 1 ; i <= m ; i++ ){
    u = Find( data[ i ].u );
    v = Find( data[ i ].v );
    if ( v != u ){
    f[ v ] = u;
    dot.w = data[ i ].w;
    dot.v = u;
    map[ v ].push_back( dot );
    dot.v = v;
    map[ u ].push_back( dot );
    }
    }
    for( int i = 1 ; i <= n ; i++ )
    if ( father[ i ][ 0 ] == 0 ) Dfs( i , 0 , INF , 1 );

    Work();

    scanf( "%d" , &q );
    for( int i = 1 ; i <= q ; i++ ){
    scanf( "%d%d" , &u , &v );
    if ( Find( u ) != Find( v ) ) printf( "-1\n" );
    else printf( "%d\n" , LCA( u , v ) );
    }
    fclose( stdin );
    fclose( stdout );
    return 0;
    }

  • 0
    @ 2015-10-19 22:29:48

    WA那么多次真是太惨了,终于长记性了。判断相不相等不应该是father[x] == father[y]而应该是getfather(x) == getfather(y)
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #include <cctype>
    #include <cstring>

    using namespace std;

    #define INF 1000000000

    struct Edge {
    int x, y, len;
    } edge[50005];

    struct Node {
    int nextNode, len;
    Node *next;
    } *N[10005], pool[10000005];

    int m, n;
    int father[10005];
    int cnt;
    bool vis[10005];
    int depth_node[100005];
    int up[10005];
    int f0[10005];

    int getfather(int x) {
    return (father[x] == x) ? x : father[x] = getfather(father[x]);
    }
    void merge(int x, int y) {
    father[getfather(x)] = y;
    }
    bool cmp(Edge a, Edge b) {
    return (a.len > b.len);
    }
    void mst() {
    sort(edge + 1, edge + m + 1, cmp);
    for (int i = 1; i <= n; ++i) {
    father[i] = i;
    }
    for (int i = 1; i <= m; ++i) {
    //printf("[%d %d %d %d]", edge[i].x, edge[i].y, getfather(edge[i].x), getfather(edge[i].y));
    if (getfather(edge[i].x) != getfather(edge[i].y)) {
    Node *p = &pool[++cnt];
    p->nextNode = edge[i].y;
    p->len = edge[i].len;
    p->next = N[edge[i].x];
    N[edge[i].x] = p;
    p = &pool[++cnt];
    p->nextNode = edge[i].x;
    p->len = edge[i].len;
    p->next = N[edge[i].y];
    N[edge[i].y] = p;
    merge(edge[i].x, edge[i].y);
    }
    }
    }
    inline int in() {
    int RV = 0;
    char p = getchar();
    while(!isdigit(p)) {
    p = getchar();
    }
    while(isdigit(p)) {
    RV *= 10;
    RV += (p - '0');
    p = getchar();
    }
    return RV;
    }
    void dfs(int k, int depth) {
    vis[k] = true;
    depth_node[k] = depth;
    for (Node *p = N[k]; p; p = p->next) {
    if (!vis[p->nextNode]) {
    dfs(p->nextNode, depth + 1);
    f0[p->nextNode] = k;
    up[p->nextNode] = p->len;
    }
    }
    }
    int lca(int a, int b) {
    int ans = INF;
    int d1 = depth_node[a], d2 = depth_node[b];
    while (a != b) {
    if (d1 > d2) {
    ans = min(up[a], ans);
    a = f0[a];
    --d1;
    }
    else {
    ans = min(up[b], ans);
    b = f0[b];
    --d2;
    }
    }
    return ans;
    }
    int main(int argc, const char *argv[]) {
    scanf("%d %d", &n, &m);
    int x, y, z;
    for (int i = 1; i <= m; ++i) {
    x = in();
    y = in();
    z = in();
    edge[i].x = x;
    edge[i].y = y;
    edge[i].len = z;
    }
    mst();
    for (int i = 1; i <= n; ++i)
    if (father[i] == i)
    dfs(i, 1);
    int q = in();
    for (int i = 1; i <= q; ++i) {
    x = in();
    y = in();
    if (getfather(x) != getfather(y))
    printf("-1\n");
    else {
    printf("%d\n", lca(x, y));
    }
    }
    return 0;
    }

    • @ 2015-10-24 20:51:09

      呵呵,这个确实容易有时候疏忽写错,不然要那个查的函数干嘛,

  • 0
    @ 2015-10-18 17:40:29

    LAC
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    #define inf 1e8
    using namespace std;
    struct Tp{
    int l,r,w;
    }p[50005];
    struct Ta{
    int x,w;
    };
    int n,m,q,fa[10005],d[10005][25],f[10005][25],deep[10005];
    bool v[10005];
    vector<Ta>a[10005];
    bool comp(const Tp x,const Tp y)
    {
    if(x.w>y.w) return true;
    return false;
    }
    int find(int x)
    {
    if(fa[x]==x) return x;
    int y=x,k;
    while(x!=fa[x])
    x=fa[x];
    while(fa[y]!=x)
    {
    k=fa[y];
    fa[y]=x;
    y=k;
    }
    return x;
    }
    void jia(int k)
    {
    Ta ta;
    int s=p[k].l,t=p[k].r;
    ta.w=p[k].w;
    ta.x=t;
    a[s].push_back(ta);
    ta.x=s;
    a[t].push_back(ta);
    }
    void dfs(int u,int de)
    {
    deep[u]=de;
    v[u]=true;
    for(int i=0;i<a[u].size();i++)
    {
    int k=a[u][i].x;
    if(!v[k])
    {
    d[k][0]=a[u][i].w;
    f[k][0]=u;
    dfs(k,de+1);
    }
    }
    }
    void make(int s,int t)
    {
    int ans=inf,k;
    if(deep[s]<deep[t])
    swap(s,t);
    while(deep[s]>deep[t])
    {
    ans=min(ans,d[s][0]);
    s=f[s][0];
    }
    while(f[s][0]!=f[t][0])
    {
    for(k=20;k>=0;k--)
    if(f[s][k]!=f[t][k])
    break;
    ans=min(ans,d[s][k]);
    ans=min(ans,d[t][k]);
    s=f[s][k];
    t=f[t][k];
    }
    if(s!=t)
    {
    ans=min(ans,d[s][0]);
    ans=min(ans,d[t][0]);
    }
    printf("%d\n",ans);
    }
    int main()
    {
    freopen("truck.in","r",stdin);
    freopen("truck.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    scanf("%d%d%d",&p[i].l,&p[i].r,&p[i].w);
    sort(p+1,p+m+1,comp);
    int k=0,i=0,x,y,fx,fy;
    for(int i=1;i<=n;i++)
    fa[i]=i;
    while(m--)
    {
    i++;
    x=p[i].l,y=p[i].r;
    fx=find(x);
    fy=find(y);
    if(fx!=fy)
    {
    fa[fx]=fy;
    k++;
    jia(i);
    }
    }
    memset(v,0,sizeof(v));
    for(int i=1;i<=n;i++)
    if(!v[i])
    dfs(i,1);
    ////
    for(int k=1;k<=20;k++)
    for(int i=1;i<=n;i++)
    {
    d[i][k]=min(d[i][k-1],d[f[i][k-1]][k-1]);
    f[i][k]=f[f[i][k-1]][k-1];
    }
    ////////
    int s,t;
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
    scanf("%d%d",&s,&t);
    if(find(s)==find(t))
    make(s,t);
    else printf("-1\n");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
    }

  • 0
    @ 2015-10-12 09:27:22

    笨的人不用写倍增也能过 跑的不慢

    要求最小边最大 跑一遍kruskal 求一个最大生成树
    并且要把这棵树建出来 建出来的树可能是森林 所以加一个超级根
    然后暴力往上走给定的两个点 一边走一边跟新答案 一直走到lca
    如果他们的lca是那个超级根 那么说明不连通 输出-1

    有人说要用树上倍增 蒟蒻表示不会 所以想写个暴力看看得多少分
    不小心AC了 而且跑的也不慢 真是无语

    type
    arr=record
    long,v,next:longint;
    end;
    var
    t:array[0..20009] of arr;
    h,deep,last,fa:array[0..10009] of longint;
    bb:array[0..10009] of boolean;
    a,b,c:array[0..50009] of longint;
    x,y,gen,af,bf,tot,n,m,i:longint;
    procedure swap(var a,b:longint);
    var ti:longint;
    begin
    ti:=a; a:=b; b:=ti;
    end;
    procedure sort(l,r:longint);
    var i,j,bi:longint;
    begin
    i:=l; j:=r; bi:=c[(l+r) div 2];
    repeat
    while c[i]>bi do inc(i);
    while c[j]<bi do dec(j);
    if i<=j then
    begin
    swap(a[i],a[j]); swap(b[i],b[j]); swap(c[i],c[j]);
    inc(i); dec(j);
    end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
    end;
    procedure built(x,y,z:longint);
    begin
    inc(tot);
    t[tot].v:=y;
    t[tot].long:=z;
    t[tot].next:=last[x];
    last[x]:=tot;
    end;
    function find(x:longint):longint;
    begin
    if fa[x]=x then exit(x);
    fa[x]:=find(fa[x]);
    exit(fa[x]);
    end;
    procedure bfs;
    var tou,wei,x,j:longint;
    begin
    fillchar(bb,sizeof(bb),true);
    h[1]:=gen; deep[gen]:=0; bb[gen]:=false;
    tou:=0; wei:=1;
    while tou<wei do
    begin
    inc(tou);
    j:=last[h[tou]];
    while j<>0 do
    begin
    x:=t[j].v;
    if bb[x]=true then
    begin
    bb[x]:=false;
    deep[x]:=deep[h[tou]]+1;
    inc(wei); h[wei]:=x;
    end;
    j:=t[j].next;
    end;
    end;
    end;
    function lca(x,y:longint):longint;
    var p,ans,j,ti:longint;
    begin
    ans:=100000000;
    if deep[x]>deep[y] then
    begin ti:=x; x:=y; y:=ti; end;
    while deep[y]>deep[x] do
    begin
    j:=last[y];
    while j<>0 do
    begin
    p:=t[j].v;
    if deep[p]<deep[y] then
    begin
    y:=p;
    if t[j].long<ans then ans:=t[j].long;
    end;
    j:=t[j].next;
    end;
    end;
    if x=y then exit(ans);
    while x<>y do
    begin
    j:=last[y];
    while j<>0 do
    begin
    p:=t[j].v;
    if deep[p]<deep[y] then
    begin
    y:=p;
    if t[j].long<ans then ans:=t[j].long;
    end;
    j:=t[j].next;
    end;
    j:=last[x];
    while j<>0 do
    begin
    p:=t[j].v;
    if deep[p]<deep[x] then
    begin
    x:=p;
    if t[j].long<ans then ans:=t[j].long;
    end;
    j:=t[j].next;
    end;
    end;
    if (x=gen) and (y=gen) then exit(-1) else exit(ans);
    end;
    begin
    //assign(input,'1.in'); reset(input);
    readln(n,m);
    for i:=1 to m do read(a[i],b[i],c[i]);
    sort(1,m);
    for i:=1 to n do fa[i]:=i;
    i:=0; tot:=0;
    while i<m do
    begin
    inc(i);
    af:=find(a[i]); bf:=find(b[i]);
    if af<>bf then
    begin
    fa[af]:=bf;
    built(a[i],b[i],c[i]);
    built(b[i],a[i],c[i]);
    end;
    end;
    gen:=n+1;
    fa[gen]:=gen;
    for i:=1 to n do
    if find(i)<>gen then
    begin
    fa[find(i)]:=gen;
    built(i,gen,0);
    built(gen,i,0);
    end;
    bfs;
    read(m);
    for i:=1 to m do
    begin
    read(x,y);
    writeln(lca(x,y));
    end;
    end.

    • @ 2015-11-04 11:28:16

      不连通不是可以用并查集来说明么?你生成树的时候不是已经知道点是否在集合内了,如果fa不一样就输出-1。如果在同棵树这样枚举其实也算是朴素的LCA吧?不需要超级根啊?

  • 0
    @ 2015-10-05 21:27:24

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n,m,fa[10005],f[10005][16],Con[10005][15],d[10005],p;
    bool vi[10005];
    struct node{
    int x,y,z;
    bool operator<(const node &tmp)const{
    return tmp.z<z;
    }
    }a[50005];
    struct Edge{
    int to,dis;
    Edge *next;
    };
    Edge *E[10005],Pr[20005];int cnt;
    void addedge(int u,int v,int w){
    Pr[++cnt].to=v;Pr[cnt].dis=w;Pr[cnt].next=E[u];E[u]=&Pr[cnt];
    Pr[++cnt].to=u;Pr[cnt].dis=w;Pr[cnt].next=E[v];E[v]=&Pr[cnt];
    }
    int find(int i){
    if (fa[i]==i) return i;
    return fa[i]=find(fa[i]);
    }
    void Init(){
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a,a+m);
    for (int i=1;i<=n;i++) fa[i]=i;
    // for (int i=0;i<m;i++) cout<<a[i].x<<' '<<a[i].z<<endl;
    }
    void Build(){
    for (int i=0;i<m;i++){
    int u=find(a[i].x);
    int v=find(a[i].y);
    if (u!=v){
    fa[u]=v;
    addedge(a[i].x,a[i].y,a[i].z);
    // cout<<a[i].x<<' '<<a[i].y<<' '<<a[i].z<<endl;
    }
    }
    }
    void update(int i){
    for (int j=1;j<=15&&f[i][j-1]!=-1;j++){
    f[i][j]=f[f[i][j-1]][j-1];
    // cout<<i<<' '<<j<<endl;
    Con[i][j]=min(Con[i][j-1],Con[f[i][j-1]][j-1]);
    }
    }
    void DFS(int u){
    // cout<<u<<endl;
    update(u);
    for (Edge *P=E[u];P;P=P->next){
    if (vi[P->to]){
    vi[P->to]=false;
    d[P->to]=d[u]+1;
    f[P->to][0]=u;
    Con[P->to][0]=P->dis;
    DFS(P->to);
    }
    }
    }
    int query(int x,int y){
    if (d[x]>d[y])swap(x,y);
    int ans1=2147364836;
    int ans2=2147364836;
    for (int j=15;j>=0;j--)
    if (d[f[y][j]]>=d[x]){
    ans2=min(ans2,Con[y][j]);
    y=f[y][j];
    }
    if (x==y)return min(ans1,ans2);
    for (int j=15;j>=0;j--)
    if (f[x][j]!=f[y][j]){
    ans1=min(ans1,Con[x][j]);
    ans2=min(ans2,Con[y][j]);
    x=f[x][j];y=f[y][j];
    }
    ans1=min(ans1,Con[x][0]);
    ans2=min(ans2,Con[y][0]);
    return min(ans1,ans2);
    }
    void Work(){
    memset(f,-1,sizeof(f));
    memset(vi,true,sizeof(vi));vi[0]=false;
    for (int i=1;i<=n;i++) d[i]=-1;
    for (int i=1;i<=n;i++){
    if (d[i]==-1){
    // cout<<i<<endl;
    addedge(0,i,-1);
    DFS(0);
    }
    }
    /* for (int i=1;i<=n;i++) cout<<d[i]<<' ';cout<<endl;
    for (int i=1;i<=n;i++){
    for (int j=0;j<=15;j++) cout<<f[i][j]<<' ';
    cout<<endl;
    }
    for (int i=1;i<=n;i++){
    for (int j=0;j<=15;j++) cout<<Con[i][j]<<' ';
    cout<<endl;
    }*/
    scanf("%d",&p);
    for (int i=0;i<p;i++){
    int x,y;
    scanf("%d%d",&x,&y);
    printf("%d\n",query(x,y));
    }

    }
    int main(){
    Init();
    Build();
    Work();
    }

  • 0
    @ 2015-10-03 15:07:42

    Block code

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int inf=0x3f3f3f3f;
    const int N=10010,M=50050;
    inline int min(int a,int b) {return a<b?a:b;}
    inline int max(int a,int b) {return a>b?a:b;}
    inline int read() {
    int f=1,x=0; 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 f*x;
    }
    struct Edge{
    int to,v,n;
    }e[M<<1]; int tot=0,head[N];
    bool cmp(const Edge&a,const Edge&b) {return a.n>b.n;}
    int n,m,q;
    int fa[N][15],D[N][15],len[N];
    int f[N];
    bool vis[N];
    void Init() {
    n=read(), m=read();
    for(int i=1;i<=n;++i) f[i]=i;
    for(int i=1;i<=m;++i)
    e[M+i].to=read(),
    e[M+i].v=read(),
    e[M+i].n=read();
    q=read();
    sort(e+M+1,e+M+m+1,cmp);
    memset(D,0x3f,sizeof(D));
    }

    int Find(int s) {
    return f[s]==s?s:f[s]=Find(f[s]);
    }
    inline void Add_E(int x,int y,int v) {
    e[++tot]=(Edge) {y,v,head[x]}, head[x]=tot;
    e[++tot]=(Edge) {x,v,head[y]}, head[y]=tot;
    }

    void DFS(int s,int l) {
    vis[s]=true, len[s]=l;
    for(int p=head[s]; p; p=e[p].n) if(!vis[e[p].to]){
    int now=e[p].to;
    fa[now][0]=s, D[now][0]=e[p].v;
    DFS(now,l+1);
    }
    }
    inline void C(int tp,int &x,int &ans) {
    for(int k=13;k>=0;--k) {
    if(tp<(1<<k)) continue;
    ans=min(ans,D[x][k]),
    x=fa[x][k];
    tp-=(1<<k);
    }
    }
    inline int Ans() {
    int x=read(),y=read(),ans=inf;
    if(Find(x)!=Find(y)) return -1;
    int tp=len[x]-len[y];
    if(tp>0) C(tp,x,ans);
    else if(tp<0) C(-tp,y,ans);
    if(x==y) return ans;
    for(int k=13;k>=0;--k) {
    if(fa[x][k]==fa[y][k]) continue;
    ans=min(min(D[x][k],D[y][k]),ans);
    x=fa[x][k], y=fa[y][k];
    }
    return min(min(D[x][0],D[y][0]),ans);
    }
    void Solve() {
    int pos=M+m,u,v;
    for(int i=M+1;i<=pos;++i) {
    Find(u=e[i].to),
    Find(v=e[i].v);
    if(f[u]==f[v]) continue;
    f[f[v]]=f[u], Add_E(u,v,e[i].n);
    }
    for(int i=1;i<=n;++i) if(!vis[i])
    DFS(Find(i),0);
    for(int k=1;k<=13;++k) {
    int nowlen=1<<k;
    for(int i=1;i<=n;++i) if(len[i]>=nowlen)
    fa[i][k]=fa[fa[i][k-1]][k-1],
    D[i][k]=min(D[fa[i][k-1]][k-1],D[i][k-1]);
    }
    for(int i=0;i<q;++i)
    printf("%d\n",Ans());
    }
    int main() {
    //freopen("tmp.txt","r",stdin);
    Init();
    Solve();
    return 0;
    }
    缩行狂魔...我...

  • 0
    @ 2015-09-27 22:21:47

    ###好吧,其实这道题也不是很难,然而因为种种细节,我错了很多次。
    ###解法在网上铺天盖地,其实就是克鲁斯卡尔算法加倍增,不用倍增只能得60分;

    记录信息
    评测状态 Accepted
    题目 P1843 货车运输
    递交时间 2015-09-27 22:12:12
    代码语言 C++
    评测机 VijosEx
    消耗时间 2284 ms
    消耗内存 13948 KiB
    评测时间 2015-09-27 22:12:16
    评测结果
    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 13948 KiB, score = 5
    测试数据 #1: Accepted, time = 0 ms, mem = 13944 KiB, score = 5
    测试数据 #2: Accepted, time = 15 ms, mem = 13944 KiB, score = 5
    测试数据 #3: Accepted, time = 15 ms, mem = 13944 KiB, score = 5
    测试数据 #4: Accepted, time = 15 ms, mem = 13944 KiB, score = 5
    测试数据 #5: Accepted, time = 15 ms, mem = 13944 KiB, score = 5
    测试数据 #6: Accepted, time = 57 ms, mem = 13944 KiB, score = 5
    测试数据 #7: Accepted, time = 46 ms, mem = 13940 KiB, score = 5
    测试数据 #8: Accepted, time = 46 ms, mem = 13944 KiB, score = 5
    测试数据 #9: Accepted, time = 46 ms, mem = 13940 KiB, score = 5
    测试数据 #10: Accepted, time = 46 ms, mem = 13944 KiB, score = 5
    测试数据 #11: Accepted, time = 48 ms, mem = 13948 KiB, score = 5
    测试数据 #12: Accepted, time = 250 ms, mem = 13948 KiB, score = 5
    测试数据 #13: Accepted, time = 250 ms, mem = 13944 KiB, score = 5
    测试数据 #14: Accepted, time = 234 ms, mem = 13944 KiB, score = 5
    测试数据 #15: Accepted, time = 234 ms, mem = 13944 KiB, score = 5
    测试数据 #16: Accepted, time = 250 ms, mem = 13944 KiB, score = 5
    测试数据 #17: Accepted, time = 234 ms, mem = 13944 KiB, score = 5
    测试数据 #18: Accepted, time = 234 ms, mem = 13940 KiB, score = 5
    测试数据 #19: Accepted, time = 234 ms, mem = 13948 KiB, score = 5
    Accepted, time = 2284 ms, mem = 13948 KiB, score = 100
    代码
    #include <iostream>
    #include <string.h>
    #include <stdio.h>
    #include <algorithm>
    using namespace std;
    int f[100010];
    struct point{
    int u,v,dist;
    }edge[100010];
    int fa[100010][23];
    int best[10010][23];
    int dst[100010];
    int nxt[100010];
    int to[100010];
    int fir[100010];
    int deep[100010];
    int cnt=1;
    int n,k;
    bool cmp(point a,point b)
    {
    return a.dist>b.dist;
    }
    int find(int x){
    if(f[x]==x)return x;
    else return f[x]=find(f[x]);
    }
    void add(int a,int b,int dist)
    {
    nxt[cnt]=fir[a];
    to[cnt]=b;
    dst[cnt]=dist;
    fir[a]=cnt++;
    }
    void dfs(int now)
    {
    for(int i=fir[now];i;i=nxt[i])
    if(fa[now][0]!=to[i]){
    fa[to[i]][0]=now;
    best[to[i]][0]=dst[i];
    deep[to[i]]=deep[now]+1;
    dfs(to[i]);
    }
    }
    int main()
    {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=k;i++)
    scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].dist);
    sort(edge+1,edge+k+1,cmp);
    int x,y;
    for(int i=1;i<=k;i++)
    if((x=find(edge[i].u))!=(y=find(y=edge[i].v))){
    f[x]=y;
    add(edge[i].u,edge[i].v,edge[i].dist);
    add(edge[i].v,edge[i].u,edge[i].dist);
    }
    memset(best,127,sizeof(best));
    for(int i=1;i<=n;i++)fa[i][0]=i; //这里必须赋初值
    dfs(1);
    for(int k=1;k<=20;k++)
    for(int i=1;i<=n;i++)
    { fa[i][k]=fa[fa[i][k-1]][k-1];
    best[i][k]=min(best[i][k-1],best[fa[i][k-1]][k-1]);
    }
    int Q;
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    if(find(a)!=find(b)){
    printf("-1\n");
    continue;
    }
    if(deep[a]<deep[b]){
    swap(a,b);
    }
    int ans=0x3f3f3f3f;
    int d=deep[a]-deep[b];
    int x=a,y=b;
    for(int k=0;k<=20;k++){

    if((d>>k)%2==1){

    ans=min(ans,best[x][k]);
    x=fa[x][k];
    }
    }
    for(int k=20;x!=y&&k>=0;k--){
    if(fa[x][k]!=fa[y][k]||k==0){
    ans=min(best[x][k],ans);
    ans=min(best[y][k],ans);
    x=fa[x][k];
    y=fa[y][k];
    if(k==0)k++;
    }
    } //这里要注意,当k=0时,如果循环没退出,必须再找一次k=0,不断循环……
    printf("%d\n",ans);
    }
    }

  • 0
    @ 2015-09-18 18:55:18

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<algorithm>
    using namespace std;
    vector<int>yu[10000];
    int n,m;
    int q;
    int sum;
    int ok[10000];
    int d[10000][10000];
    void yuxiating(int x,int y,int tot)
    {
    if(x==y){sum=max(tot,sum);return ;}
    for(int i=0;i<yu[x].size();i++)
    {

    int tot1=min(tot,d[x][yu[x][i]]);
    yuxiating(i,y,tot1);
    }

    }
    int main()
    {
    cin>>n>>m;
    int count1=0;
    for(int i=0;i<m;i++)
    {int x,y,z;
    cin>>x>>y>>z;
    yu[x].push_back(y);
    yu[y].push_back(x);
    d[x][y]=z;
    d[y][x]=z;
    }

    cin>>q;

    for(int i=0;i<q;i++){
    int ii,o;
    cin>>ii>>o;
    sum=0;

    yuxiating(ii,o,10000);

    if(sum){
    ok[count1++]=sum;}
    else{
    ok[count1++]=-1;
    }

    }
    for(int i=0;i<count1;i++)
    {
    cout<<ok[i]<<"\n";
    }
    return 0;

    }

    为什么不对

信息

ID
1843
难度
7
分类
(无)
标签
递交数
5317
已通过
953
通过率
18%
被复制
9
上传者