作者:鬼鬼太子_157 | 来源:互联网 | 2023-05-17 20:24
题目大意:给定一个矩阵,有一些关键点,每个格子有权值,选择一些格子使所有关键点连通,求最小权值和传说中的斯坦纳树--感觉不是很难理解的样子枚举连通的状态,对于每个状态先对每个位置枚举
题目大意:给定一个矩阵,有一些关键点,每个格子有权值,选择一些格子使所有关键点连通,求最小权值和
传说中的斯坦纳树- - 感觉不是很难理解的样子
枚举连通的状态,对于每个状态先对每个位置枚举子集进行合并,然后对这个状态的分层图进行SPFA
看了几分代码还是ZKY写的比较简洁- -
此外就是终于能通过操作符重载访问结构体里的三维数组了- - 我真是太丧病了233
#include
#include
#include
#include
#define M 15
#define INF 0x3f3f3f3f
using namespace std;
struct abcd{
int x,y,sta;
abcd() {}
abcd(int _,int __,int ___):
x(_),y(__),sta(___) {}
bool operator ! () const
{
return x==0 && y==0 && sta==0 ;
}
}q[65540];
templateclass Reader{
private:
struct Subreader{
T memory[M][1<<10];
T* operator [] (int x)
{
return memory[x];
}
}memory[M];
public:
T& operator [] (const abcd &x)
{
return memory[x.x][x.y][x.sta];
}
Subreader& operator [] (int x)
{
return memory[x];
}
};
int m,n,cnt;
int map[M][M];
bool mark[M][M];
Reader f;
Reader v;
Reader from;
unsigned short r,h;
void SPFA()
{
static const int dx[]={1,-1,0,0};
static const int dy[]={0,0,1,-1};
int i;
while(r!=h)
{
abcd x=q[++h];v[x]=0;
for(i=0;i<4;i++)
{
abcd y(x.x+dx[i],x.y+dy[i],x.sta);
if(y.x<=0||y.x>m||y.y<=0||y.y>n)
continue;
if(f[y]>f[x]+map[y.x][y.y])
{
f[y]=f[x]+map[y.x][y.y];
from[y]=x;
if(!v[y])
v[y]=1,q[++r]=y;
}
}
}
}
void Steiner_Tree()
{
int i,j,k,sta;
for(sta=1;sta<1< {
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
for(k=sta&sta-1;k;k=sta&k-1)
if(f[i][j][sta]>f[i][j][k]+f[i][j][sta-k]-map[i][j])
{
f[i][j][sta]=f[i][j][k]+f[i][j][sta-k]-map[i][j];
from[i][j][sta]=abcd(i,j,k);
}
if(f[i][j][sta]!=INF)
q[++r]=abcd(i,j,sta),v[i][j][sta]=1;
}
SPFA();
}
}
void DFS(abcd x)
{
if(!from[x]) return ;
mark[x.x][x.y]=1;
abcd temp=from[x];
DFS(temp);
if( x.x==temp.x && x.y==temp.y )
DFS(abcd(temp.x,temp.y,x.sta-temp.sta) );
}
int main()
{
int i,j;
cin>>m>>n;
memset(&f,0x3f,sizeof f);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
if(!map[i][j])
f[i][j][1< }
Steiner_Tree();
try{
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
if(!map[i][j])
throw(true);
}catch(bool) {}
abcd temp(i,j,(1< cout< DFS(temp);
for(i=1;i<=m;i++,puts("") )
for(j=1;j<=n;j++)
{
if(!map[i][j])
putchar('x');
else if(mark[i][j])
putchar('o');
else
putchar('_');
}
return 0;
}