POJ 1789&&2485&&1258&&3026-白红宇

POJ 1789&&2485&&1258&&3026

阅读量：5068 次

发布时间：2019-06-12

本文共 2288 字，大约阅读时间需要 7 分钟。

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

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

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

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

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

　　1789CODE

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N=2005;struct data{    int x,num;    bool operator <(const data s) const    {        return s.x
          
            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=0; for (int i=0;i
           
            >n; k=ans=0; if (!n) break; for (i=1;i<=n;++i) cin>>s[i]; for (i=1;i

　　2485CODE

#include
     
      #include
      
       using namespace std;const int N=505;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=0; char ch=getchar();    while (ch<'0'||ch>'9') ch=getchar();    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();}inline void write(int x){    if (x/10) write(x/10);    putchar(x%10+'0');}inline int comp(data a,data b){    return a.s

　　1258CODE

#include
     
      #include
      
       using namespace std;const int N=505;struct data{    int x,y,s;}a[N*N];int n,i,j,k,x,father[N],ans;inline void read(int &x){    x=0; char ch=getchar();    while (ch<'0'||ch>'9') ch=getchar();    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();}inline void write(int x){    if (x/10) write(x/10);    putchar(x%10+'0');}inline int comp(data a,data b){    return a.s

　　3026CODE

#include
     
      #include
      
       #include
       
        using namespace std;const int N=155,fx[4]={
   1,0,-1,0},fy[4]={
   0,1,0,-1};struct data{    int x,y,s;}e[N*N];int i,j,n,m,t,k,q[N*N*10][2],step[N][N],father[N*N],ans;bool vis[N][N];char a[N][N];inline void BFS(int x,int y){    int head=0,tail=1;    memset(vis,0,sizeof(vis));    q[1][0]=x; q[1][1]=y; vis[x][y]=1; step[x][y]=0;    while (head
        
         0&&yyy>0&&xxx<=n&&yyy<=m)             {                vis[xxx][yyy]=1;                 step[xxx][yyy]=step[xx][yy]+1;                q[++tail][0]=xxx; q[tail][1]=yyy;            }        }    }}inline int comp(data a,data b){    return a.s