题解

55 条题解

  • 0
    @ 2016-07-13 14:56:45

    先并查集搜索有无环,然后把环内的点搜索一遍确定最短环
    #include <iostream>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <algorithm>
    using namespace std;
    int n, x;
    queue<int> q;
    int way[200001], fa[200001];
    int f[200001];
    int find(int x) {
    if(fa[x] != x)
    return fa[x] = find(fa[x]);
    return x;
    }
    int work() {
    int top = q.front(), x = q.front();
    q.pop();
    f[top] = 0;
    x = way[x];
    f[x] = 1;
    while(x != top) {
    int k = x;
    x = way[x];
    f[x] = f[k] + 1;
    }
    return f[top];
    }
    int main() {
    cin >> n;
    for(int i = 1; i <= n; i++)
    cin >> way[i], fa[i] = i;
    for(int i = 1; i <= n; i++) {
    int uu = find(way[i]);
    if(uu == i)
    q.push(i);
    else fa[i] = uu;
    }
    int min1 = 2147483647;
    while(!q.empty()) {
    if(f[q.front()] != 0)
    q.pop();
    else min1 = min(work(), min1);
    }
    cout << min1 << endl;
    return 0;
    }

  • 0
    @ 2016-07-05 08:08:37

    直接暴力标记秒切
    什么tarjan一边去
    var
    i,j,k,o,p,n,m,x,y,ans:longint;
    a,b,c,d:array[0..1000000]of longint;
    begin
    ans:=maxlongint;
    readln(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do
    begin
    if c[i]>0 then continue;
    x:=i;
    y:=1;
    while true do
    begin
    if c[x]>0 then
    begin
    if (c[x]=i)and(y-b[x]<ans) then ans:=y-b[x];
    break;
    end;
    b[x]:=y;
    c[x]:=i;
    x:=a[x];
    inc(y);
    end;
    end;
    writeln(ans);
    end.

  • 0
    @ 2016-06-23 14:58:56
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    const int maxn = 200000 + 100;
    int n;
    int ans = 99999999;
    int m;
    int tot;
    struct mem {
        int to;
        int vis1;
        int vis2;
        int d;
    } s[maxn];
    
    void dfs (int r, int cnt) {
        if (s[r].vis2 == m) {
            ans = min (ans, tot - s[r].d);
        } 
        else if (s[r].vis1) return;
        else {
            s[r].vis1 = 1;
            s[r].vis2 = m;
            s[r].d = tot;
            dfs (s[r].to, tot++);
        }
    }
    
    int main ()
    {
        //freopen ("in.txt", "r", stdin);
        cin >> n;
        for (int i = 1; i <= n; i++) scanf ("%d", &s[i].to);
        for (m = 1; m <= n; m++) {
            if (!s[m].vis1) {
                dfs (m, tot++);
            }
        }
        cout << ans;
        return 0;
    }
    
  • 0
    @ 2016-03-24 13:35:16
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #define INF 0x3f3f3f3f
    #define N 200005
    using namespace std;
    int n,ans,t,a[N],ti[N],vis2[N];
    bool vis1[N];
    void dfs(int k,int cnt){
        if (vis2[k]==t){
            ans=min(ans,cnt-ti[k]);
            return;
        }else{
            if (vis1[k]) return; 
                else{
                    vis1[k]=1;
                    vis2[k]=t;
                    ti[k]=cnt;
                    dfs(a[k],cnt+1);
                }
        }
    }
    int main(){
        scanf("%d",&n);
        ans=INF;
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        for (int i=1;i<=n;i++){
            if (!vis1[i]){
                t++;
                dfs(i,1);
            }
        }
        printf("%d\n",ans);
        return 0;
    }
    
    
  • 0
    @ 2016-03-20 10:58:25

    并不清楚考试的时候随便打的竟然可以100分-.-
    var a,fin,fout,f,q:array[1..200001] of longint;
    n,i,j,k,min,l:longint;
    team:array[1..500000] of longint;
    s:array[1..200000] of boolean;
    procedure main;
    var i,j,m:longint;
    ok:boolean;
    begin
    m:=1;
    for j:=1 to n do begin
    if (fin[j]>0) then begin
    dec(fin[j]);
    i:=j;ok:=false;
    end else continue;
    while fout[i]<>0 do begin
    inc(k);
    team[k]:=i;
    dec(fout[i]);
    dec(fin[a[i]]);
    i:=a[i];
    ok:=true;
    end;
    if ok then begin
    inc(k);
    team[k]:=i;
    q[m]:=k;
    inc(m);
    inc(k);
    team[k]:=0;
    end;
    end;
    end;

    begin

    readln(n);
    min:=maxlongint;
    for i:=1 to n do begin
    read(a[i]);
    inc(fin[a[i]]);
    inc(fout[i]);
    end;
    main;
    l:=1;
    for i:=1 to k do begin
    if team[i]=0 then begin inc(l);continue;end;
    if team[q[l]]=team[i] then
    if (q[l]-i<min)and(q[l]<>i) then min:=q[l]-i;
    end;
    writeln(min);

    end.

  • 0
    @ 2015-11-29 16:29:48

    并查集优化代码
    var
    father,road:array[1..1000000]of longint;
    a:array[1..1000000] of longint;
    flag:array[1..1000000]of boolean;
    i,j,k,ans,p,now,n:longint;
    function getfather(x:longint):longint;
    begin
    if father[x]=x then exit(x);
    father[x]:=getfather(father[x]);
    exit(father[x]);
    end;
    procedure merge(x,y:longint);
    var xx,yy:longint;
    begin
    xx:=getfather(x);
    yy:=getfather(y);
    father[xx]:=yy;
    end;
    function judge(x,y:longint):boolean;
    var xx,yy:longint;
    begin
    xx:=getfather(x);
    yy:=getfather(y);
    exit(xx=yy);
    end;
    procedure findround(k:longint);
    begin
    //road[k]:=1;
    now:=0;
    p:=k;
    while not flag[p] do
    begin
    flag[p]:=true;
    inc(now);
    road[p]:=now;
    p:=a[p];
    end;
    if (ans>now-road[p]+1) then
    ans:=now-road[p]+1;
    end;
    begin
    readln(n);
    fillchar(flag,sizeof(flag),0);
    for i:=1 to n do father[i]:=i;
    for i:=1 to n do
    begin
    read(a[i]);
    if not judge(i,a[i]) then
    merge(a[i],i);
    end;
    readln;
    ans:=maxlongint shr 1;
    for i:=1 to n do
    if father[i]=i then
    findround(i);
    writeln(ans);
    end.

  • 0
    @ 2015-11-23 10:45:48

    var
    msg,stp:array[1..200000] of longint;
    flag,p:array[1..200000] of boolean;
    i,j,k,n,tmp,val:longint;
    hr:boolean;
    begin
    assign(input,'message.in'); reset(input);
    assign(output,'message.out'); rewrite(output);
    readln(n);
    val:=maxlongint;
    for i:=1 to n do read(msg[i]);
    fillchar(p,sizeof(p),false);
    for i:=1 to n do
    begin
    if p[i] then continue;
    j:=i;
    fillchar(flag,sizeof(flag),false);
    k:=0;
    hr:=true;
    while not flag[j] do
    begin
    if p[j] then
    begin
    hr:=false;
    break;
    end;
    flag[j]:=true;
    p[j]:=true;
    inc(k);
    stp[j]:=k;
    j:=msg[j];
    end;

    if hr then
    begin
    tmp:=k-stp[j]+1;
    if tmp<val then val:=tmp;
    end;
    end;
    writeln(val);
    close(input);
    close(output);
    end.

  • 0
    @ 2015-11-20 15:26:15

    我发一个容易看懂的题解吧
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    bool v[200100];
    int a[200100],n,m,ru[200100],k,ans=1,minn=9999999;
    void search(int x,int y)
    {
    int p,t;
    if(x==y) return;
    if(!v[y]) v[y]=true;
    if(!v[x]) {
    v[x]=true;
    ans++;
    search(a[x],y);
    }
    }
    int main()
    {
    int i,j;
    memset(v,false,sizeof(v));

    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
    scanf("%d",&a[i]);
    ru[a[i]]++;
    }
    while(1)
    { k=1;
    for(i=1;i<=n;i++)
    if(ru[i]==0&&!v[i])
    {
    k=0;
    v[i]=true;
    ru[a[i]]--;
    }
    if(k==1) break;
    }

    for(i=1;i<=n;i++)
    if(!v[i]) {
    search(a[i],i);
    if(minn>ans) minn=ans;
    ans=1;
    }

    printf("%d",minn);

    return 0;
    }

  • 0
    @ 2015-11-19 17:57:56

    求最小环,从每一点尝试dfs,如果在本次dfs中发现再次访问了在本次被访问过的节点,那么说明存在一个环,环的长度就是这个节点被两次访问时的迭代次数之差。只要一次被dfs后就不再访问这个节点,由于每个点只被访问一次,这样的时间效率就是O(n),轻松AC。

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    long ans,ansn;
    long road[200001];
    bool f[200001];
    long p[200001];
    long t[200001];
    void dfs(long x,long s,long ct)
    {
    if (!f[x]){
    f[x]=true; t[x]=s; p[x]=ct; dfs(road[x],s+1,ct);
    } else{
    if (s-t[x]<ans && ct==p[x]) ans=s-t[x];
    }
    }
    int main()
    {
    long n,i;
    cin>>n;
    for (i=1;i<=n;i++)
    scanf("%ld",&road[i]);
    memset(f,false,sizeof(f));
    ans=n;
    for (i=1;i<=n;i++)
    if (!f[i])dfs(i,0,i);
    printf("%ld",ans);
    return 0;
    }

  • 0
    @ 2015-11-18 23:16:41

    Floyd判圈算法+vis数组标记小优化
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    const int MAXN = 2e5 + 5;
    bool vis[MAXN];
    int t[MAXN];
    int n, ans = MAXN;
    void Floyd(int i) {
    vis[i] = 1;
    if (vis[t[i]]) return;
    int cur1 = i, cur2 = i;
    int cnt = 0;
    do {
    cur1 = t[cur1];
    vis[cur1] = 1;
    cur2 = t[t[cur2]];
    } while (cur1 != cur2);
    do {
    cur1 = t[cur1];
    ++cnt;
    cur2 = t[t[cur2]];
    } while (cur1 != cur2);
    ans = min(ans, cnt);

    }
    int main() {
    memset(vis, 0, sizeof(vis));
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &t[i]);
    for (int i = 1; i <= n; ++i) if (!vis[i]) Floyd(i);
    printf("%d\n", ans);
    return 0;
    }

    • @ 2015-11-20 14:38:13

      洛谷上测最后一个点超时

  • 0
    @ 2015-11-17 13:12:42

    真的只要剪一下枝就好了啊......
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    using namespace std;

    int n;
    int minn=10000000;

    int t[200000+5]={0};
    int s[200000+5]={0};
    int can[200000+5]={0};
    int c[200000+5]={0};

    int tt=-1;

    inline int min(int a,int b)
    {
    if(a<b)return a;
    return b;

    }

    void dfs(int now,int step)
    {
    if(can[now]==tt)
    {
    minn=min(minn,step-s[now]);
    return ;

    }
    can[now]=tt;
    s[now]=step;
    dfs(t[now],step+1);

    }

    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&t[i]);
    c[t[i]]++;
    }

    for(int i=1;i<=n;i++)
    {
    if(can[i]==0)
    {
    if(c[i]!=0)
    {
    s[i]=1;
    dfs(i,1);
    tt--;
    }
    else c[t[i]]--;
    }
    }
    printf("%d",minn);

    //while(1);

    return 0;

    }

  • 0
    @ 2015-11-16 20:39:52

    求最小环,反正从一个点出只有一个环,去掉入度为0的点然后DFS就好了。为什么我TM考试写得bellmon-ford!!!然后就爆炸了
    ps:windows环境会爆栈,然后最后一个点RE,linux是没问题的可以AC,懒得写人工栈。。。
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #define maxn 200010
    bool vis[maxn];
    int t[maxn],count[maxn];
    int ans(1<<29),tar(99999);
    int dfs(int s)
    {
    if(!vis[s])
    {
    vis[s]=true;
    int x=dfs(t[s]);
    if(x!=1<<25 && s!=tar)
    return x+1;
    else if(s==tar) {
    ans=std::min(ans,x);
    return 1<<25;
    }
    vis[s]=false;
    }
    else {
    tar=s;
    return 1;}
    return 1<<25;
    }
    int main()
    {
    int n;
    scanf("%d",&n);
    memset(count,0,sizeof(count));
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&t[i]);
    count[t[i]]++;
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
    if(!vis[i] && count[i]>0)
    dfs(i);
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2015-11-14 20:39:58

    直接搜索,搜索的同时记录
    开数组记录点:没搜过、不在环内、在环内(记录环的长度)
    对于一个新的以前没搜过的点x 搜到下列三种情况停止:
    1. 搜索到这次循环新遍历到的点y,即出现新的环
    2. 之前记录的环上的节点y
    3. 之前记录的非环上的点y

    对于1: 从x到y之前的点标为环外,对于剩下的点标环的长度
    对于2、3: 这次搜到的全标成环外
    一直搜到所有点都搜过

    最后暴搜所有点
    找环内点记录的环的长度的最小值
    输出即可
    每个点走常数次
    O(n)

  • 0
    @ 2015-11-14 18:57:58

    考试的时候没什么思路,知道是求最小环(画有向图)写了个递推。70%能过

    后来写斗地主的时候发现不对劲,这道题可能涉及多个连通块。说到连通块,我想到并查集,于是一发不可收拾找到了时间复杂度n的算法。

    因为对于每个连通块来说都一定有出度。因此从一个连通块任意位置出发。第一个点记1,第二个为2,请把样例1的图画起来跟我这样模拟。我们给2号点记为3,4为4,5为5,然后又回到了2.此时应记6,但是2之前已经有记为3了。那么ans:=now-x
    now为目前记的值。x为之前的数。也就是说如果X不为0就可以计算ans。然后退出。这就是最小环?为什么?因为我们发现。一个连通块只能有一个环!!

    那么这就是n的算法,对每个连通块扫一遍即可。连通块的判断用并查集。对每棵树从根扫描。当然不用并查集也可以的

    pascal代码等我比赛程序发回来再发...
    ###pascal code
    program message1;
    var n,i,ans,ans2:longint;
    t,a,fa:array[1..200000] of longint;
    function find(x:longint):longint;
    begin
    if fa[x]=x then exit(x);
    fa[x]:=find(fa[x]); find:=fa[x];
    end;

    procedure add(x,y:longint);
    begin
    x:=find(x); y:=find(y);
    fa[y]:=x;
    end;

    procedure search(now,s:longint);
    begin
    if a[now]<>0 then begin ans:=s-a[now]; if ans<ans2 then ans2:=ans; exit; end;
    if a[now]=0 then a[now]:=s;
    search(t[now],s+1);
    end;
    begin
    read(n);
    for i:=1 to n do fa[i]:=i;
    for i:=1 to n do begin read(t[i]); add(i,t[i]); end;
    fillchar(a,sizeof(a),0); ans2:=maxlongint;
    for i:=1 to n do
    if fa[i]=i then
    search(i,1);
    write(ans2);
    end.

    • @ 2015-11-18 17:28:31

      有没有c++代码

    • @ 2015-11-20 18:12:49

      **手动从Pascal翻译成的C++

      不知道为什么耗时要比Pascal**高

      代码如下
      #include<iostream>

      using namespace std;
      const int maxn=200000;

      int aim[maxn],dis[maxn]={0},root[maxn];
      int fa[maxn];
      int ans=maxn+1;

      int father(int p){
      if (fa[p]==p) return p;
      fa[p]=father(fa[p]);
      return fa[p];
      }

      void add(int a,int b){
      fa[father(b)]=father(a);
      }

      void work(int p){
      int i=1;
      dis[p]=i;
      while (true){
      p=aim[p];
      i++;
      if (dis[p]>0){
      if (i-dis[p]<ans)
      ans=i-dis[p];
      break;
      }
      else dis[p]=i;
      }
      }

      int main(){
      int n,i;

      cin>>n;
      for (i=0;i<n;i++) fa[i]=i;
      for (i=0;i<n;i++){
      cin>>aim[i];
      add(i,--aim[i]);
      }

      int p=0;
      for (i=0;i<n;i++)
      if (fa[i]==i)
      root[p++]=i;

      for (i=0;i<p;i++) work(root[i]);
      cout<<ans<<"\n";

      return 0;
      }

  • 0
    @ 2015-11-10 17:49:08

    是简单的搜索,选择一个数i,不断的访问其后续,并记录步数k,将节点i压入栈中,mark=true。如果要访问的节点mark[ti]==true那么开始弹出栈内元素,如果弹出的元素等于ti那么ans=min(ans,k-k[ti]+1);一个个元素向下走。直到每个元素的mark==true。运算步数最小为2n,最多为3n时间复杂度为O(n) 对于n<=200000的情况可以AC。
    别问我为什么第二题的算法像Tarjan,我本来就是在求环(单向的强连通分量),正确性是在于每个节点只有一条路径离开!所以形成的强连通分量一定是一个单向环!
    #define _CRT_SECURE_NO_DEPRECATE
    #include<iostream>
    #include<cstdio>
    #include<fstream>
    using namespace std;

    long n,head,d,step,ans=200006;
    long t[200005] = { 0 }, k[200005] = { 0 },s[200005];
    bool mark[200005] = { false };

    int main()
    {
    cin >> n;
    for (int i = 1; i <= n; i++)
    scanf("%ld", &t[i]); //cin的效率好像比较低
    for (int i = 1; i <= n; i++)
    {
    head = 1;
    d = i;
    step = 0;
    mark[d] = true;
    k[d] = 0;
    s[head] = d;
    while (!mark[t[d]])
    {
    step++;
    d = t[d];
    head++;
    s[head] = d;
    k[d] = step;
    mark[d] = true;
    }
    while (head--)
    if (s[head] == t[d])
    {
    ans = ans > k[d] - k[s[head]] + 1 ? k[d] - k[s[head]] + 1 : ans;
    break;
    }
    }
    cout << ans;
    // system("pause"); 这个是VS编译时候出来的,忽略掉
    return 0;
    }

信息

ID
1979
难度
6
分类
(无)
标签
递交数
4096
已通过
980
通过率
24%
被复制
9
上传者