2016山东省NOI省队集训DAY4 题目题解数据标程 NOIP省选集训

2016山东省NOI省队集训DAY4 题目题解数据标程 NOIP省选集训

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int inf=453266144F1[4]={001-1}F2[4]={1-100};
int a[20][20]ansV[20][20]dp[17][17][1<<7]b[3005]d[20][20]c[305]nmKijTSsumkrlnowxnowy;
bool v[20][20];
struct node {int xyz;} st[1000005];
int cmp（node inode j） {return i.z>j.z;}
int main（）
{
	freopen（“graph.in““r“stdin）;
	freopen（“graph.out““w“stdout）;
    srand（10086）;
    ans=inf;
    scanf（“%d%d%d“&n&m&K）;
    for （i=1; i<=n; i++）
      for （j=1; j<=m; j++）
      {
        scanf（“%d“&a[i][j]）;
        if （a[i][j]!=-1） a[i][j]++;
        assert（a[i][j]>=-1 && a[i][j]<=n*m）;
      }
    for （i=1; i<=n; i++）
      for （j=1; j<=m; j++）
        scanf（“%d“&V[i][j]）;
    T=380; sum=n*m;
    for （i=1; i<=sum; i++） b[i]=i;
    for （i=0; i<=n+1; i++） for （j=0; j<=m+1; j++） if （i<=0 || i>n || j<=0 || j>m） d[i][j]=-1;
    while （T--）
    {
       random_shuffle（b+1b+n*m+1）;
       for （i=1; i<=K; i++） c[b[i]]=i;
       for （i=K+1; i<=sum; i++） c[b[i]]=rand（）%K+1;
       for （i=1; i<=n; i++） for （j=1; j<=m; j++） d[i][j]=c[a[i][j]]-1;
       S=（1<       for （i=1; i<=n; i++） for （j=1; j<=m; j++） for （k=0; k       for （i=1; i<=n; i++）
         for （j=1; j<=m; j++）
           if （d[i][j]>=0） dp[i][j][1<      for （i=1; i      {
          for （l=（i-1&i）; l+l>i; l=（l-1&i））
            for （j=1; j<=n; j++）
              for （k=1; k<=m; k++）
                dp[j][k][i]=min（dp[j][k][i]dp[j][k][l]+dp[j][k][i^l]-V[j][k]）;
          r=0;
          for （j=1; j<=n; j++） for （k=1; k<=m; k++） v[j][k]=false;
          for （j=1; j<=n; j++）
            for （k=1; k<=m; k++）
              if （dp[j][k][i]              {
                st[++r].x=j; st[r].y=k;
                v[j][k]=true;
              }
          l=0;
          while （l!=r）
          {
              nowx=st[++l].x; nowy=st[l].y;
              for （j=0; j<4; j++）
                if （d[nowx+F1[j]][nowy+F2[j]]>=0 && dp[nowx][nowy][i]+V[nowx+F1[j]][nowy+F2[j]]dp[nowx][nowy][i]+V[nowx+F1[j]][nowy+F2[j]]）
                {
                    dp[nowx+F1[j]][nowy+F2[j]][i]=dp[nowx][nowy][i]+V[nowx+F1[j]][nowy+F2[j]];
                    if （!v[nowx+F1[j]][nowy+F2[j]]） {st[++r].x=nowx+F1[j]; st[r].y=nowy+F2[j];v[nowx+F1[j]][nowy+F2[j]]=true;}
                }
              v[nowx][nowy]=false;
          }
          for （j=1; j<=n; j++） for （k=1; k<=m; k++）
            for （l=0; l<4; l++）
              if （d[j+F1[l]][k+F2[l]]>=0 && dp[j+F1[l]][k+F2[l]][i|（1<dp[j][k][i]+V[j+F1[l]][k+F2[l]]）
                dp[j+F1[l]][k+F2[l]][i|（1<      }
      for （j=1; j<=n; j++） for （k=1; k<=m; k++） ans=min（ansdp[j][k][S-1]）;
    }
    if （ans==inf） puts

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2019-04-08 23:02  data\
     文件         470  2016-05-26 12:44  data\dataconf.xml
     文件        3054  2016-05-25 19:58  data\graph.cpp
     文件          83  2016-05-25 19:27  data\graph1.in
     文件           3  2016-05-25 19:27  data\graph1.out
     文件        1991  2016-05-25 19:33  data\graph10.in
     文件           7  2016-05-25 19:34  data\graph10.out
     文件         157  2016-05-25 19:28  data\graph2.in
     文件           7  2016-05-25 19:28  data\graph2.out
     文件        1876  2016-05-18 10:46  data\graph3.in
     文件           8  2016-05-18 10:51  data\graph3.out
     文件        1857  2016-05-25 19:30  data\graph4.in
     文件           8  2016-05-25 19:30  data\graph4.out
     文件        1870  2016-05-25 19:30  data\graph5.in
     文件           8  2016-05-25 19:30  data\graph5.out
     文件         275  2016-05-25 19:31  data\graph6.in
     文件           8  2016-05-25 19:32  data\graph6.out
     文件         269  2016-05-25 19:32  data\graph7.in
     文件           7  2016-05-25 19:32  data\graph7.out
     文件         274  2016-05-25 19:32  data\graph8.in
     文件           8  2016-05-25 19:32  data\graph8.out
     文件        2051  2016-05-18 10:46  data\graph9.in
     文件           7  2016-05-25 19:34  data\graph9.out
     文件        3384  2016-05-25 19:54  data\rabbits.cpp
     文件          69  2016-05-25 19:49  data\rabbits1.in
     文件           3  2016-05-25 19:49  data\rabbits1.out
     文件          93  2016-05-25 19:50  data\rabbits10.in
     文件          11  2016-05-25 19:53  data\rabbits10.out
     文件          98  2016-05-20 13:35  data\rabbits2.in
     文件           5  2016-05-25 19:47  data\rabbits2.out
     文件          98  2016-05-20 13:35  data\rabbits3.in
............此处省略43个文件信息