简单题 并查集找下就行
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
#define LL long long
int fa[];
int w[][],o[][];
char s[][];
int find(int x)
{
if(x!=fa[x])
fa[x] = find(fa[x]);
return fa[x];
}
int main()
{
int i,j,n,a,d;
LL sum=;
scanf("%d",&n);
scanf("%d%d%*c",&d,&a);
for(i = ; i <= n ; i++)
fa[i] = i;
for(i = ; i <= n ; i++)
for(j = ; j <= n ; j++)
cin>>s[i][j];
for(i = ;i <= n ; i++)
for(j = i+ ; j <= n ; j++)
{
if(s[i][j]=='')
{
int tx = find(i);
int ty = find(j);
if(tx==ty)
{
o[i][j] = ;
o[j][i] = ;
if(!w[i][j])
{
w[i][j] = w[j][i] = ;
sum+=d;
}
}
else
fa[tx] = ty;
}
}
int t = ;
for(i = ;i <= n ; i++)
{
if(fa[i]==i)
{
if(t)
{
o[t][i] = ;
o[i][t] = ;
if(!w[t][i])
{
w[t][i] = w[i][t] = ;
sum+=a;
}
}
t = i;
}
}
printf("%lld\n",sum);
for(i = ; i <= n ; i++)
{
for(j = ; j <= n ;j++)
{
if(o[i][j]==)
printf("d");
else if(o[i][j]==)
printf("a");
else
printf("");
}
puts("");
}
return ;
}