POJ 1789&&2485&&1258&&3026

　　这个真的太水了——MST专辑。

　　如果不会MST的两种算法的同学可以出门右转了。

　　大致讲一下，第一题我是用Prim+堆优化的（毕竟点比较多），后面三题用的是Kruskal（习惯打，而且并查集常数实在小）

　　前三题是裸题，最后一题要BFS预处理图上两点间的最短距离再跑Kruskal，稍微麻烦了点

　　按顺序贴自己看吧（第四题数据有坑，数组要开大）

　　1789CODE

#include<cstdio>

#include<string>

#include<queue>

#include<iostream>

#include<cstring>

using namespace std;

const int N=;

struct data

{

    int x,num;

    bool operator <(const data s) const

    {

        return s.x<x;

    }

};

struct edge

{

    int to,next,v;

}e[N*N];

priority_queue <data> tree;

int head[N],dis[N],n,i,j,k,ans;

string s[N];

bool vis[N];

inline int calc(int x,int y)

{

    int res=;

    for (int i=;i<s[x].size();++i)

    if (s[x][i]!=s[y][i]) res++;

    return res;

}

inline void add(int x,int y,int z)

{

    e[++k].to=y; e[k].v=z; e[k].next=head[x]; head[x]=k;

}

int main()

{

    for (;;)

    {

        memset(e,-,sizeof(e));

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

        memset(vis,,sizeof(vis));

        memset(dis,,sizeof(dis));

        cin>>n; k=ans=;

        if (!n) break;

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

        cin>>s[i];

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

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

        {

            int res=calc(i,j);

            add(i,j,res); add(j,i,res);

        }

        dis[]=;

        data p;

        p.x=; p.num=;

        tree.push(p);

        while (!tree.empty())

        {

            int now=tree.top().num;

            tree.pop();

            if (vis[now]) continue;

            vis[now]=; ans+=dis[now];

            for (i=head[now];i!=-;i=e[i].next)

            if (e[i].v<dis[e[i].to])

            {

                dis[e[i].to]=e[i].v;

                data p;

                p.x=dis[e[i].to]; p.num=e[i].to;

                tree.push(p);

            }

        }

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

    }

    return ;

}

　　2485CODE

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=;

struct data

{

    int x,y,s;

}a[N*N];

int t,n,i,j,k,x,father[N],ans;

inline void read(int &x)

{

    x=; char ch=getchar();

    while (ch<''||ch>'') ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

}

inline void write(int x)

{

    if (x/) write(x/);

    putchar(x%+'');

}

inline int comp(data a,data b)

{

    return a.s<b.s;

}

inline int getfather(int k)

{

    return father[k]==k?k:father[k]=getfather(father[k]);

}

int main()

{

    read(t);

    while (t--)

    {

        read(n);

        ans=k=;

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

        for (j=;j<=n;++j)

        {

            read(x);

            if (i==j) continue;

            a[++k].x=i; a[k].y=j; a[k].s=x;

        }

        sort(a+,a+k+,comp);

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

        father[i]=i;

        for (i=;i<=k;++i)

        {

            int fx=getfather(a[i].x),fy=getfather(a[i].y);

            if (fx!=fy)

            {

                ans=a[i].s;

                father[fx]=fy;

            }

        }

        write(ans); putchar('\n');

    }

    return ;

}

　　1258CODE

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=;

struct data

{

    int x,y,s;

}a[N*N];

int n,i,j,k,x,father[N],ans;

inline void read(int &x)

{

    x=; char ch=getchar();

    while (ch<''||ch>'') ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

}

inline void write(int x)

{

    if (x/) write(x/);

    putchar(x%+'');

}

inline int comp(data a,data b)

{

    return a.s<b.s;

}

inline int getfather(int k)

{

    return father[k]==k?k:father[k]=getfather(father[k]);

}

int main()

{

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

    {

        ans=k=;

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

        for (j=;j<=n;++j)

        {

            read(x);

            if (i==j) continue;

            a[++k].x=i; a[k].y=j; a[k].s=x;

        }

        sort(a+,a+k+,comp);

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

        father[i]=i;

        for (i=;i<=k;++i)

        {

            int fx=getfather(a[i].x),fy=getfather(a[i].y);

            if (fx!=fy)

            {

                ans+=a[i].s;

                father[fx]=fy;

            }

        }

        write(ans); putchar('\n');

     }

    return ;

}

　　3026CODE

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=,fx[]={,,-,},fy[]={,,,-};

struct data

{

    int x,y,s;

}e[N*N];

int i,j,n,m,t,k,q[N*N*][],step[N][N],father[N*N],ans;

bool vis[N][N];

char a[N][N];

inline void BFS(int x,int y)

{

    int head=,tail=;

    memset(vis,,sizeof(vis));

    q[][]=x; q[][]=y; vis[x][y]=; step[x][y]=;

    while (head<tail)

    {

        int xx=q[++head][],yy=q[head][];

        if (a[xx][yy]=='S'||a[xx][yy]=='A') e[++k].x=(x-)*m+y,e[k].y=(xx-)*m+yy,e[k].s=step[xx][yy];

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

        {

            int xxx=xx+fx[i],yyy=yy+fy[i];

            if (!vis[xxx][yyy]&&a[xxx][yyy]!='#'&&xxx>&&yyy>&&xxx<=n&&yyy<=m)

            {

                vis[xxx][yyy]=;

                step[xxx][yyy]=step[xx][yy]+;

                q[++tail][]=xxx; q[tail][]=yyy;

            }

        }

    }

}

inline int comp(data a,data b)

{

    return a.s<b.s;

}

inline int getfather(int k)

{

    return father[k]==k?k:father[k]=getfather(father[k]);

}

int main()

{

    scanf("%d\n",&t);

    while (t--)

    {

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

        for (k=,ans=,i=;i<=n*m;++i)

        father[i]=i;

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

        {

            for (j=;j<=m;++j)

            a[i][j]=getchar();

            getchar();

        }

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

        for (j=;j<=m;++j)

        if (a[i][j]=='S'||a[i][j]=='A') BFS(i,j);

        sort(e+,e+k+,comp);

        for (i=;i<=k;++i)

        {

            int fax=getfather(e[i].x),fay=getfather(e[i].y);

            if (fax!=fay)

            {

                ans+=e[i].s;

                father[fax]=fay;

            }

        }

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

    }

}

巴特西

POJ 1789&&2485&&1258&&3026

最新文章

热门文章