bzoj 2595: [Wc2008]游览计划

wc！！！斯坦纳树！！！！！！！！！！！！！！！！！！！！
while (1) {iq--，膝盖++；}
还是不太理解的样子。。。。（过几天自己就会了，，不虚（大雾））
  1 #include<cstdio>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<map>
  5 #include<queue>
  6 #define N 1000005
  7 #define inf 1000000000
  8 #define LL long long
  9 using namespace std;
 10 int a[15][15];
 11 int bin[20];
 12 int n,m,K;
 13 int f[12][12][1024];
 14 struct data{
 15     int fir,sed,thd;
 16 }pre[15][15][1024];
 17 int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
 18 queue<pair<int , int > >q;
 19 bool inq[15][15],vis[15][15];
 20 void spfa(int st)
 21 {
 22     while (!q.empty())
 23     {
 24         int x=q.front().first,y=q.front().second;
 25         inq[x][y]=0; q.pop();
 26         for (int k=0; k<4; k++)
 27         {
 28             int nowx=x+xx[k],nowy=y+yy[k];
 29             if (nowx<1 || nowy<1 || nowx>n || nowy>m) continue;
 30             if (f[nowx][nowy][st]>f[x][y][st]+a[nowx][nowy])
 31             {
 32                 f[nowx][nowy][st]=f[x][y][st]+a[nowx][nowy];
 33                 pre[nowx][nowy][st]=(data){x,y,st};
 34                 if (!inq[nowx][nowy])
 35                 {
 36                     q.push(make_pair(nowx,nowy));
 37                     inq[nowx][nowy]=1;
 38                 }
 39             }
 40         }
 41     }
 42 }
 43 void dfs(int x, int y, int st)
 44 {
 45     if (x>inf || pre[x][y][st].thd==0) return;
 46     vis[x][y]=1;
 47     data t=pre[x][y][st];
 48     dfs(t.fir,t.sed,t.thd);
 49     if (t.fir==x && t.sed==y) dfs(x,y,st-t.thd);
 50 }
 51 int main()
 52 {
 53     bin[0]=1; for (int i=1; i<20; i++) bin[i]=bin[i-1]<<1;
 54     scanf("%d%d",&n,&m);
 55     for (int i=1; i<=n; i++)    
 56         for (int j=1; j<=m; j++)
 57         {
 58             scanf("%d",&a[i][j]);
 59             if (!a[i][j]) K++;
 60         }
 61     for (int i=1; i<=n; i++)
 62         for (int j=1; j<=m; j++)
 63             for (int k=0; k<bin[K]; k++)
 64                 f[i][j][k]=pre[i][j][k].fir=inf;
 65     K=0;
 66     for (int i=1; i<=n; i++)
 67         for (int j=1; j<=m; j++)
 68             if (!a[i][j]) f[i][j][bin[K++]]=0;
 69     for (int st=1; st<bin[K]; st++)
 70     {
 71         for (int i=1; i<=n; i++)
 72             for (int j=1; j<=m; j++)
 73             {
 74                 for (int s=st&(st-1);s;s=st&(s-1))
 75                 {
 76                     int t=f[i][j][s]+f[i][j][st-s]-a[i][j];      //?????
 77                     if (t<f[i][j][st])
 78                     {
 79                         printf("%d %d %d",i,j,s); while (1);
 80                         f[i][j][st]=t;
 81                         pre[i][j][st]=(data){i,j,s};
 82                     }
 83                 }
 84                 if (f[i][j][st]<inf) q.push(make_pair(i,j)),inq[i][j]=1;
 85             }
 86             spfa(st);
 87     }
 88     int x,y;
 89     for (int i=1; i<=n; i++)
 90         for (int j=1; j<=m; j++)
 91             if (!a[i][j])
 92             {
 93                 x=i; y=j; break;
 94             }
 95     dfs(x,y,bin[K]-1);
 96     printf("%d
",f[x][y][bin[K]-1]);
 97     for (int i=1; i<=n; i++)
 98     {
 99         for (int j=1; j<=m; j++)
100         {
101             if (!a[i][j]) printf("x");
102             else if (vis[i][j]) printf("o");
103             else printf("_");
104         }
105         puts("");
106     }
107     return 0;
108 }