存边代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
struct Edge{
    int from,to,val;
};
std::vector<Edge> edges[MAXN];
void add(int from,int to,int val){
    Edge e={from,to,val};
    edges[from].push_back(e);
}
int main(){
    int n,m,k,w;
    cin>>n>>m>>k>>w;
    std::vector<std::vector<string>> s(k,std::vector<string>(n));
    std::vector<std::vector<int>> dis(k,std::vector<int>(k,n*m));
    //std::vector<int> fa(k,0);
    for (int i = 0; i < k; ++i)
    {
        dis[i][i]=0;
        for (int j = 0; j < n; ++j)
        {
            cin>>s[i][j];
        }
    }
    int res=0;
    std::vector<bool> vis(k,false);
    std::vector<pair<int,int>> ans;
    priority_queue<tuple<int,int,int>,std::vector<tuple<int,int,int>>,greater<>> pq;
    for (int i = 0; i < k; ++i)
    {
        for (int j = i+1; j < k; ++j)
        {
            int cost=0;
            for (int x = 0; x < n; ++x)
            {
                for (int y = 0; y < m; ++y)
                {
                    if(s[i][x][y]!=s[j][x][y])  cost+=w;
                }
            }
            dis[i][j]=min(dis[i][j],cost);
            dis[j][i]=dis[i][j];
        }
    }
    auto prim=[&]()
    {
        pq.push({n*m,0,0});
        while(!pq.empty())
        {
            auto [d,id,fa]=pq.top();
            pq.pop();
            if(vis[id]) continue;
            vis[id]=true;
            res+=d;
            if(d==n*m)
            {
                ans.push_back({id+1,0});
            }
            else
            {
                ans.push_back({id+1,fa+1});
            }
            for (int i = 0; i < k; ++i)
            {
                if(vis[i])  continue;
                pq.push({dis[id][i],i,id});
            }
        }
    };
    prim();
    cout<<res<<"\n";
    for (int i = 0; i < ans.size(); ++i)
    {
        cout<<ans[i].first<<" "<<ans[i].second<<"\n";
    }
}

现算代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
struct Edge{
    int from,to,val;
};
std::vector<Edge> edges[MAXN];
void add(int from,int to,int val){
    Edge e={from,to,val};
    edges[from].push_back(e);
}
int main(){
    int n,m,k,w;
    cin>>n>>m>>k>>w;
    std::vector<std::vector<string>> s(k,std::vector<string>(n));
    //std::vector<std::vector<int>> dis(k,std::vector<int>(k,n*m));
    //std::vector<int> fa(k,0);
    for (int i = 0; i < k; ++i)
    {
        //dis[i][i]=0;
        for (int j = 0; j < n; ++j)
        {
            cin>>s[i][j];
        }
    }
    int res=0;
    std::vector<bool> vis(k,false);
    std::vector<pair<int,int>> ans;
    priority_queue<tuple<int,int,int>,std::vector<tuple<int,int,int>>,greater<>> pq;
    // for (int i = 0; i < k; ++i)
    // {
    //     for (int j = i+1; j < k; ++j)
    //     {
    //         int cost=0;
    //         for (int x = 0; x < n; ++x)
    //         {
    //             for (int y = 0; y < m; ++y)
    //             {
    //                 if(s[i][x][y]!=s[j][x][y])  cost+=w;
    //             }
    //         }
    //         dis[i][j]=min(dis[i][j],cost);
    //         dis[j][i]=dis[i][j];
    //     }
    // }
    auto cal=[&](int u, int v)
    {
        int diff=0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if(s[u][i][j]!=s[v][i][j])  diff+=w;
            }
        }
        return diff;
    };
    auto prim=[&]()
    {
        pq.push({n*m,0,0});
        while(!pq.empty())
        {
            auto [d,id,fa]=pq.top();
            pq.pop();
            if(vis[id]) continue;
            vis[id]=true;
            res+=d;
            if(d==n*m)
            {
                ans.push_back({id+1,0});
            }
            else
            {
                ans.push_back({id+1,fa+1});
            }
            for (int i = 0; i < k; ++i)
            {
                if(vis[i])  continue;
                int val=cal(i,id);
                pq.push({val,i,id});
            }
        }
    };
    prim();
    cout<<res<<"\n";
    for (int i = 0; i < ans.size(); ++i)
    {
        cout<<ans[i].first<<" "<<ans[i].second<<"\n";
    }
}