[kuangbin带你飞]专题六 最小生成树

学习最小生成树已经有一段时间了 做一些比较简单的题还算得心应手..花了三天的时间做完了kuangbin的专题 写一个题解出来记录一下(虽然几乎都是模板题)

做完的感想：有很多地方都要注意 n == 1

注意double 的精度问题

poj 1251 模板题 大写字母减去'A'+1即是它的编号

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

#include<queue>

using namespace std;

struct edge

{

    int u,v,w;

};

edge a[30000];

int fa[50];

int cmp(edge a,edge b)

{

    return a.w<b.w;

}

int find(int x)

{

    if(fa[x]==x)

    return x;

    return fa[x]=find(fa[x]);

}

void un(int x,int y)

{

    int fx=find(x);

    int fy=find(y);

    if(fx==fy)

    return ;

    fa[fx]=fy;

    return ;

}

int n;

int tot;

int kru()

{

    int cnt=0;

    int res=0;

    for(int i=0;i<tot;i++)

    {

        int u=a[i].u;

        int v=a[i].v;

        int w=a[i].w;

        if(find(u)!=find(v))

        {

            un(u,v);

            cnt++;

            res+=w;

        }

        if(cnt==n-1)

        return res;

    }

    return -1;

}

int main(){

while(~scanf("%d",&n))

{

    if(n==0)

    break;

    tot=0;

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

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

    {

        char u[20],v[20];

        scanf("%s",u);

        int ma;

        scanf("%d",&ma);

        int uu=u[0]-'A'+1;

        for(int k=1;k<=ma;k++)

        {

            scanf("%s",v);

            int w;

            scanf("%d",&w);

            int vv=v[0]-'A'+1;

            a[tot].u=uu;

            a[tot].v=vv;

            a[tot++].w=w;

        }

    }

    sort(a,a+tot,cmp);

    int ans=kru();

    printf("%d\n",ans);

}

}

poj 1287 极裸的kru算法

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

using namespace std;

int n,m;

int ta[70][70];

int fa[70];

struct node

{

    int u,v,w;

};

node a[2700];

int tot;

void init(){

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

}

int find(int x)

{

    if(fa[x]==x)

        return x;

    else return fa[x]=find(fa[x]);

}

void un(int x,int y)

{

    int fx=find(x);

    int fy=find(y);

    if(fx==fy)

        return ;

    fa[fx]=fy;

    return ;

}

int cmp(node a,node b)

{

    return a.w<b.w;

}

int kru()

{

    int res=0;

    int cnt=0;

    init();

    for(int i=0;i<tot;i++)

    {

        int u=a[i].u;

        int v=a[i].v;

        int w=a[i].w;

        if(find(u)!=find(v))

        {

            un(u,v);

            res+=w;

            cnt++;

        }

        if(cnt==n-1)

            return res;

    }

}

int main(){

while(scanf("%d",&n)!=EOF)

{

    if(n==0)

        break;

    scanf("%d",&m);

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

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

    {

        ta[i][k]=999999999;

        if(i==k)

            ta[i][k]=0;

    }

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

    {

        int u,v,w;

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

        if(ta[u][v]>w)

            ta[u][v]=ta[v][u]=w;

    }

    tot=0;

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

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

    {

        if(ta[i][k]!=999999999)

        {

            a[tot].u=i;

            a[tot].v=k;

            a[tot].w=ta[i][k];

            tot++;

        }

    }

    sort(a,a+tot,cmp);

    int ans=kru();

    printf("%d\n",ans);

}

}

poj 2031 给出空间站的三维坐标和它可允许的行走半径 问需要建造多长的太空走廊可以联通 kru加个判断

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

using namespace std;

int n;

struct node

{

    int u,v;

    double w;

};

int fa[105];

int tot;

node a[10050];

struct point

{

    double x,y,z;

    double r;

};

point b[105];

void init()

{

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

}

double ji(double x1,double y1,double x2,double y2)

{

    return ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

}

int find(int x)

{

    if(fa[x]==x)

        return x;

    return fa[x]=find(fa[x]);

}

void un(int x,int y)

{

    int fx=find(x);

    int fy=find(y);

    if(fx==fy)

        return ;

    fa[fx]=fy;

    return ;

}

double kru()

{

    double res=0.0;

    int cnt=0;

    init();

    for(int i=0;i<tot;i++)

    {

        int u=a[i].u;

        int v=a[i].v;

        double w=a[i].w;

        if(find(u)!=find(v))

        {

            res+=w;

            cnt++;

            un(u,v);

        }

        if(cnt==n-1)

            return res;

    }

    return -1;

}

double cmp(node aa,node bb)

{

    return aa.w<bb.w;

}

int main(){

while(~scanf("%d",&n))

{

    if(n==0)

        break;

    tot=0;

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

    {

        scanf("%lf%lf%lf%lf",&b[i].x,&b[i].y,&b[i].z,&b[i].r);

    }

    if(n==1)

        printf("0.000\n");

    else

    {

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

    {

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

        {

            int u=i;

            int v=k;

            double w=sqrt(ji(b[i].x,b[i].y,b[k].x,b[k].y)+(b[i].z-b[k].z)*(b[i].z-b[k].z));

            w-=b[i].r;

            w-=b[k].r;

            if(w<0.0)

                w=0.0;

            a[tot].u=u;

            a[tot].v=v;

            a[tot].w=w;

            tot++;

        }

    }

    sort(a,a+tot,cmp);

    double ans=kru();

    printf("%.3f\n",ans);

    }

}

}

poj 2421 给出各点之间的联系 再给出已经连好的边(这时候用un操作一下) 然后kru

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

using namespace std;

int fa[105];

int n;

int tot;

int cnt;

int ta[105][105];

void init()

{

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

}

int find(int x)

{

    if(fa[x]==x)

    return x;

    return fa[x]=find(fa[x]);

}

void un(int x,int y)

{

    int fx=find(x);

    int fy=find(y);

    if(fx==fy)

    return ;

    fa[fx]=fy;

    return ;

}

struct node

{

    int u,v,w;

};

node a[10050];

int cmp(node a,node b)

{

    return a.w<b.w;

}

int kru()

{

    int res=0;

    cnt=0;

    if(cnt==n-1)

    return res;

    for(int i=0;i<tot;i++)

    {

        int u=a[i].u;

        int v=a[i].v;

        int w=a[i].w;

        if(find(u)!=find(v))

        {

            res+=w;

            un(u,v);

            cnt++;

        }

        if(cnt==n-1)

        return res;

    }

    return -1;

}

int main(){

while(~scanf("%d",&n))

{

    init();

    cnt=0;

    tot=0;

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

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

    {

        scanf("%d",&ta[i][k]);

    }

    int m;

    scanf("%d",&m);

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

    {

        int u,v;

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

        ta[u][v]=0;

        ta[v][u]=0;

    }

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

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

    {

        if(i<k)

        {

            a[tot].u=i;

            a[tot].v=k;

            a[tot].w=ta[i][k];

            tot++;

        }

    }

    sort(a,a+tot,cmp);

    int ans=kru();

    printf("%d\n",ans);

}

}

zoj 1586 每条边都要加上u v 所喜爱的插座的价格

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

using namespace std;

int n;

int tot;

int price[1005];

int ta[1005][1005];

int fa[1005];

struct node

{

    int u,v;

    int w;

};

node a[1000050];

void init()

{

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

}

int find(int x)

{

    if(fa[x]==x)

        return x;

    return fa[x]=find(fa[x]);

}

void un(int x,int y)

{

    int fx=find(x);

    int fy=find(y);

    if(fx==fy)

    return ;

    fa[fx]=fy;

    return ;

}

int kru()

{

    init();

    int res=0;

    int cnt=0;

    for(int i=0;i<tot;i++)

    {

        int u,v,w;

        u=a[i].u;

        v=a[i].v;

        w=a[i].w;

        if(find(u)!=find(v))

        {

            un(u,v);

            res+=w;

            cnt++;

        }

        if(cnt==n-1)

            return res;

    }

    return -1;

}

int cmp(node a,node b)

{

    return a.w<b.w;

}

int main(){

int t;

scanf("%d",&t);

while(t--)

{

    scanf("%d",&n);

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

        scanf("%d",&price[i]);

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

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

    {

        scanf("%d",&ta[i][k]);

    }

    tot=0;

    if(n==1)

        printf("0\n");

    else

    {

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

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

    {

        a[tot].u=i;

        a[tot].v=k;

        a[tot].w=ta[i][k]+price[i]+price[k];

        tot++;

    }

    sort(a,a+tot,cmp);

    int ans=kru();

    printf("%d\n",ans);

    }

}

}

poj 1789 如果两个字符串相同位置上的字母不同 res就加一 开始没读懂题意而被坑

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

using namespace std;

int n;

int tot;

struct node{

int u,v,w;

};

struct code{

char s[10];

};

code b[2050];

int did(char s1[10],char s2[10])

{

    int len=7;

    int res=0;

    for(int i=0;i<len;i++)

    {

        if(s1[i]!=s2[i])

            res++;

    }

    return res;

}

node a[5000050];

int fa[2050];

void init(){

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

    fa[i]=i;

}

int find(int x)

{

    if(fa[x]==x)

        return x;

    return fa[x]=find(fa[x]);

}

void un(int x,int y)

{

    int fx=find(x);

    int fy=find(y);

    if(fx==fy)

        return ;

    fa[fx]=fy;

    return ;

}

int cmp(node a,node b)

{

    return a.w<b.w;

}

int kru(){

int res=0;

int cnt=0;

for(int i=0;i<tot;i++)

{

    int u=a[i].u;

    int v=a[i].v;

    int w=a[i].w;

    if(find(u)!=find(v))

    {

        un(u,v);

        cnt++;

        res+=w;

    }

    if(cnt==n-1)

        return res;

}

return -1;

}

int main(){

while(~scanf("%d",&n))

{

    if(n==0)

        break;

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

    {

        scanf("%s",b[i].s);

    }

    tot=0;

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

    {

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

        {

            a[tot].u=i;

            a[tot].v=k;

            a[tot].w=did(b[i].s,b[k].s);

            tot++;

        }

    }

    if(n==1)

        printf("The highest possible quality is 1/1.\n");

    else{

    init();

    sort(a,a+tot,cmp);

    int ans=kru();

    printf("The highest possible quality is 1/%d.\n",ans);

    }

}

}

poj 2349 给出点的数目和...空间跳跃传送器的个数？利用当年打机战的想象力强行A掉...

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

using namespace std;

int m,n;

struct node{

    double x;

    double y;

};

node a[505];

int fa[505];

int tot;

struct edge{

int u,v;

double w;

};

edge b[250050];

void init(){

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

}

int find(int x){

if(fa[x]==x)

    return x;

return fa[x]=find(fa[x]);

}

void un(int x,int y){

int fx=find(x);

int fy=find(y);

if(fx==fy)

    return ;

fa[fx]=fy;

return ;

}

double kru(){

int cnt=m-1;

double res=0;

double ans=0;

if(cnt==n-1)

    return res;

init();

for(int i=0;i<tot;i++){

    int u=b[i].u;

    int v=b[i].v;

    double w=b[i].w;

    if(find(u)!=find(v)){

        cnt++;

        un(u,v);

        res+=w;

        ans=w;

    }

    if(cnt==n-1){

        return ans;

    }

}

return -1;

}

int cmp(edge a,edge b){

return a.w<b.w;

}

int main(){

int t;

scanf("%d",&t);

while(t--){

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

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

        scanf("%lf%lf",&a[i].x,&a[i].y);

    }

    tot=0;

    if(n==1)

    {

        printf("0.00\n");

    }

    else{

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

        for(int k=i+1;k<=n;k++){

            int u,v;

            double w;

            u=i;

            v=k;

            w=sqrt((a[i].x-a[k].x)*(a[i].x-a[k].x)+(a[i].y-a[k].y)*(a[i].y-a[k].y));

            b[tot].u=u;

            b[tot].v=v;

            b[tot].w=w;

            tot++;

        }

    }

    sort(b,b+tot,cmp);

    /*for(int i=0;i<tot;i++){

        printf("%d %d %.2f\n",b[i].u,b[i].v,b[i].w);

    }*/

    double ans=kru();

    printf("%.2f\n",ans);

    }

}

}

poj 1751 kru 给出已经连接的边 记录一下将要连接的边

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

using namespace std;

int n,m;

struct point

{

    double x,y;

};

point po[800];

int fa[800];

int tot;

struct node

{

    int u,v;

    double w;

};

node a[640000];

void init(){

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

}

int find(int x)

{

    if(fa[x]==x)

        return x;

    return fa[x]=find(fa[x]);

}

void un(int x,int y){

int fx=find(x);

int fy=find(y);

if(fx==fy)

return ;

fa[fx]=fy;

return ;

}

int cnt;

int cmp(node a, node b)

{

    return a.w<b.w;

}

int kru(){

double res=0;

for(int i=0;i<tot;i++){

    int u=a[i].u;

    int v=a[i].v;

    double w=a[i].w;

    if(find(u)!=find(v))

    {

        un(u,v);

        cnt++;

        res+=w;

        printf("%d %d\n",u,v);

    }

    if(cnt==n-1)

        return res;

}

return -1;

}

int main(){

while(~scanf("%d",&n))

{

    tot=0;

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

    {

        scanf("%lf%lf",&po[i].x,&po[i].y);

    }

    init();

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

    {

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

        {

            a[tot].u=i;

            a[tot].v=k;

            a[tot].w=sqrt((po[i].x-po[k].x)*(po[i].x-po[k].x)+(po[i].y-po[k].y)*(po[i].y-po[k].y));

            tot++;

        }

    }

    sort(a,a+tot,cmp);

    cnt=0;

    scanf("%d",&m);

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

    {

        int u,v;

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

        if(find(u)!=find(v))

        {

            un(u,v);

            cnt++;

        }

    }

    if(cnt==n-1)

        printf("\n");

    else

    {

        int ans=kru();

    }

}

}

poj 1258 模板kru ..(虽然我是用prim打的..真的很省代码...)

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

using namespace std;

int n;

int ans;

int ta[105][105];

int dis[105];

int vis[105];

void prim(){

for(int i=1;i<=n-1;i++){

    int minn=999999999;

    int w=0;

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

        if(vis[k])

        if(dis[k]<minn){

            minn=dis[k];

            w=k;

        }

    }

    vis[w]=0;

    ans+=dis[w];

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

        if(vis[k])

        if(ta[w][k]<dis[k]){

            dis[k]=ta[w][k];

        }

    }

}

}

int main(){

while(~scanf("%d",&n)){

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

    {

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

            scanf("%d",&ta[i][k]);

    }

    ans=0;

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

        dis[i]=999999999;

        vis[i]=1;

    }

    vis[1]=0;

    dis[1]=0;

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

    {

        dis[i]=ta[i][1];

    }

    prim();

    printf("%d\n",ans);

}

}

poj 3026 kru混合bfs 因为数据范围小所以不会超时 被吃字符的原因弄得好累..需要注意的是 输入n m后 getchar会wa..因为n m后有多个空格？(网上说的)

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

#include<queue>

#include<iostream>

using namespace std;

int n,m;

int fa[105];

char a[55][55];

bool vis[55][55];

int hao[55][55];

int geshu;

struct node

{

    int u,v,w;

};

int bian;

node b[50050];

int dx[4]={0,0,-1,1};

int dy[4]={1,-1,0,0};

void bfs(int x,int y)

{

    queue<int >q;

    q.push(x);

    q.push(y);

    int tot=0;

    q.push(tot);

    vis[x][y]=false;

    int u,v,w;

    u=hao[x][y];

    while(!q.empty())

    {

        x=q.front();q.pop();

        y=q.front();q.pop();

        tot=q.front();q.pop();

        tot++;

        int xx,yy;

        for(int i=0;i<4;i++)

        {

            xx=x+dx[i];yy=y+dy[i];

            if(xx>=0&&xx<n&&yy>0&&yy<m)

            {

                if(vis[xx][yy]==true)

                {

                    if(a[xx][yy]!='#')

                    {

                        vis[xx][yy]=false;

                        if(a[xx][yy]!=' ')

                        {

                            v=hao[xx][yy];

                            w=tot;

                            b[bian].u=u;

                            b[bian].v=v;

                            b[bian].w=w;

                            bian++;

                        }

                        q.push(xx);

                        q.push(yy);

                        q.push(tot);

                    }

                }

            }

        }

    }

}

void init(){

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

}

int find(int x)

{

    if(fa[x]==x)

        return x;

    return fa[x]=find(fa[x]);

}

void un(int x,int y)

{

    int fx=find(x);

    int fy=find(y);

    if(fx==fy)

        return ;

    fa[fx]=fy;

    return ;

}

int cmp(node a,node b)

{

    return a.w<b.w;

}

int kru(){

int res=0;

int cnt=0;

for(int i=0;i<bian;i++)

{

    int u=b[i].u;

    int v=b[i].v;

    int w=b[i].w;

    if(find(u)!=find(v))

    {

        un(u,v);

        cnt++;

        res+=w;

    }

    if(cnt==geshu-1)

        return res;

}

return -1;

}

int main(){

int t;

scanf("%d",&t);

while(t--)

{

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

    char tr[55];

    gets(tr);

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

      {

          gets(a[i]);

      }

    bian=0;

    geshu=0;

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

    {

        for(int k=0;k<m;k++)

        {

            if(a[i][k]=='A'||a[i][k]=='S')

            {

                geshu++;

                hao[i][k]=geshu;

            }

        }

    }

    init();

    //printf("%d\n",geshu);

    if(geshu==1){

        printf("0\n");

    }

    else{

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

    {

        for(int k=0;k<m;k++)

        {

            if(a[i][k]=='A'||a[i][k]=='S')

            {

                memset(vis,true,sizeof(vis));

                bfs(i,k);

            }

        }

    }

    sort(b,b+bian,cmp);

    int ans=kru();

    printf("%d\n",ans);

    }

}

}

poj 1679 到连接第n-1条边的时候找一下 是否有多条边满足？

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

using namespace std;

int n,m;

int fa[105];

int tot;

struct node

{

    int u,v,w;

};

node a[10050];

void init()

{

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

}

int find(int x)

{

    if(fa[x]==x)

        return x;

    return fa[x]=find(fa[x]);

}

void un(int x,int y)

{

    int fx=find(x);

    int fy=find(y);

    if(fx==fy)

        return ;

    fa[fx]=fy;

    return ;

}

int cmp(node a,node b)

{

    return a.w<b.w;

}

int kru()

{

    int res=0;

    int cnt=0;

    init();

    for(int i=0; i<tot; i++)

    {

        int u=a[i].u;

        int v=a[i].v;

        int w=a[i].w;

        if(find(u)!=find(v))

        {

            res+=w;

            int many=0;

            if(cnt==n-2)

            {

                for(int k=i; a[k].w==a[i].w; k++)

                {

                    if(find(a[k].u)!=find(a[k].v))

                    {

                        many++;

                    }

                }

                if(many==1)

                {

                    un(u,v);

                    return res;

                }

                else return -1;

            }

            else

            {

                un(u,v);

            }

            cnt++;

        }

        if(cnt==n-1)

            return res;

    }

    return -1;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

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

        tot=0;

        int u,v,w;

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

        {

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

            a[tot].u=u;

            a[tot].v=v;

            a[tot].w=w;

            tot++;

        }

        if(n==1)

            printf("0\n");

        else{

        sort(a,a+tot,cmp);

        int ans=kru();

        if(ans==-1)

            printf("Not Unique!\n");

        else printf("%d\n",ans);

        }

    }

}

hdu 1233 kru的模板懒得放代码了...

hdu 1301 和第一道题是同一道..

hdu 1875 有限制条件 判断一下即可

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

using namespace std;

int n;

int tot;

int fa[105];

void init()

{

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

}

int find(int x)

{

    if(fa[x]==x)

        return x;

    return fa[x]=find(fa[x]);

}

void un(int x,int y)

{

    int fx=find(x);

    int fy=find(y);

    if(fx==fy)

    return ;

    fa[fx]=fy;

    return ;

}

struct point

{

    double x;

    double y;

};

point po[105];

struct node

{

    int u,v;

    double w;

};

node a[10050];

int cmp(node a,node b)

{

    return a.w<b.w;

}

double kru(){

init();

double res=0;

int cnt=0;

int i;

for(i=0;i<tot;i++)

{

    if(a[i].w<10.0)

        continue;

    if(a[i].w>1000.0)

        break;

    int u,v;

    double w;

    u=a[i].u;

    v=a[i].v;

    w=a[i].w;

    if(find(u)!=find(v))

    {

        cnt++;

        res+=w;

        un(u,v);

    }

    if(cnt==n-1)

        return res;

}

return -1;

}

int main(){

int t;

scanf("%d",&t);

while(t--)

{

    scanf("%d",&n);

    tot=0;

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

    {

        scanf("%lf%lf",&po[i].x,&po[i].y);

    }

    if(n==1)

        printf("0.0\n");

    else

    {

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

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

    {

        a[tot].u=i;

        a[tot].v=k;

        a[tot].w=sqrt((po[i].x-po[k].x)*(po[i].x-po[k].x)+(po[i].y-po[k].y)*(po[i].y-po[k].y));

        tot++;

    }

    sort(a,a+tot,cmp);

    double ans=kru();

    int many=0;

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

    {

        if(fa[i]==i)many++;

    }

    ans*=100.0;

    if(many==1)

        printf("%.1f\n",ans);

    else printf("oh!\n");

    }

}

}