BZOJ 2595 斯坦那树

时间：2024-10-30 11:06:50

很久以前就想做，后来弃坑了。

最近又在群里有人问了类似的问题，艾老师说是斯坦纳树(％％％)

就是状压DP,然后用Spfa对状态进行转移.

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #include <queue>

 using namespace std;

 const int Maxn=;

 const int Maxm=;

 const int Inf=0x3f3f3f3f;

 const int Px=;

 const int Py=;

 const int dx[]={,,,-};

 const int dy[]={,-,,};

 //==================================

 int n,m,K,Sta,g[Maxn][Maxn],f[Maxn][Maxn][Maxm],pre[Maxn][Maxn][Maxm],STA[Maxn][Maxn];

 bool used[],Ans[Maxn][Maxn];

 queue<int> Q;

 inline int Calc(int x,int y,int s) {return x*Px+y*Py+s;}

 inline bool Check(int a,int b) {return (a|b)==a;}

 inline bool Judge(int x,int y) {return (x>= && x<=n) && (y>= && y<=m);}

 void Spfa(int sta)

 {

     while (!Q.empty())

     {

         int u=Q.front(); Q.pop();

         int x=u/Px,y=u%Px/Py;

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

         {

             int p=x+dx[d],q=y+dy[d];

             int r=sta|STA[p][q];

             if (!Judge(p,q)) continue;

             if (f[p][q][r]>f[x][y][sta]+g[p][q])

             {

                 f[p][q][r]=f[x][y][sta]+g[p][q];

                 pre[p][q][r]=u;

                 int k=Calc(p,q,r);

                 if (!used[k] && sta==r) used[k]=true,Q.push(k);

             }

         }

         used[u]=false;

     }

 }

 void Init(int x,int y,int sta)

 {

     Ans[x][y]=true;

     int k=pre[x][y][sta];

     if (!k) return;

     int i=k/Px,j=k%Px/Py,s=k%Px%Py;

     Init(i,j,s);

     if (i==x && j==y) Init(i,j,sta-s);

 }

 void Out()

 {

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

     {

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

             if (Ans[i][j])

                 if (g[i][j]) putchar('o'); else putchar('x');

              else putchar('_');

         putchar('\n');

     }

 }

 int main()

 {

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

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

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

             for (int k=;k<=(<<);k++) f[i][j][k]=Inf;

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

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

         {

             scanf("%d",&g[i][j]);

             if (!g[i][j]) STA[i][j]=(<<(K++)),f[i][j][STA[i][j]]=;

         }

     Sta=(<<K);

     for (int sta=;sta<Sta;sta++)

     {

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

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

             {

                 for (int s=;s<sta;s++)

                     if (Check(sta,s))

                         if (f[i][j][sta]>f[i][j][s]+f[i][j][sta-s]-g[i][j])

                         f[i][j][sta]=f[i][j][s]+f[i][j][sta-s]-g[i][j],

                         pre[i][j][sta]=Calc(i,j,s);

                 if (f[i][j][sta]!=Inf)

                 Q.push(Calc(i,j,sta)),used[Calc(i,j,sta)]=true;

             }

         Spfa(sta);

     }

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

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

             if (!g[i][j])

             {

                 printf("%d\n",f[i][j][Sta-]);

                 Init(i,j,Sta-);

                 Out();

                 return ;

             }

     return ;

 }

C++

相关文章