世界名画陈列馆问题

陈列馆问题"/>

世界名画陈列馆问题

我的思路是仿照 poj2811的熄灯问题。可以发现，如果第一行确定了，下面的排列问题也会确定，那么就简单多了，我们只需要枚举第一行就可以了。总共从 0-pow(2,m)（二进制表示该范围内的数，如果是1，证明该位放置机器人，否则不放置，然后把他周围放置2，2代表被看守。）
不过原题是优化枚举的做法，为了使用分支限界法qwq，我把他们搞进一个优先队列里，每次拿最小的，然后剪枝（类似启发式的搜索，大佬说，分支限界法的优先队列就是类似 dijkstra的堆优化，我深以为然qwq）
搞了好久，比方说在结构体里放数组，就是我以前从没写过的，太暴力了qwq
。。
这个做法是错误的。。（上面的是错的qwq ，如果不允许重复的话会有一大片空缺，允许重复的话会重复的不可理喻，）
关于世界名画陈列馆问题，有两个分支。
一个是允许重复，一种是不允许重复。
允许重复的可以再更多的数据中得到结果。
而不允许重复的则有很多数据得不到结果
允许重复是一种二分图匹配&网络流问题，网上常见的是用匈牙利算法写的，应该用网络流算法也能写。。有机会再写。
不允许重复的策略是把整体分为多少块（因为不会重复，所以分块一点没事，但是网上的这个代码也错了。。）
自己留着改把。。
第一个代码错误：


（11是对的， 12是第一份代码的，发现最优解并不遵循我说的规则）

#include <bits/stdc++.h>
using namespace std;
/* 模仿熄灯问题。发现第一行如果确定了，其他的行依次确定。所以只需要枚举第一行，为了使用优先队列，采用了一种启发式策略。即每次先搜索 第一行最少的使用次数。但这是不对的，因为当上面一行为空时，我们可以选择不在他下面放1，可以再他下一行的下一行放1，或者在他下一行的左边放1，或者在他下一行的右边放1，
事实上最优解的构成也是这样创建的。
*/
const int maxn=200;
int m,n;
int ans2[maxn][maxn];
int ans;
struct Node{int set2[maxn][maxn];int loc;int sum;//用来保存结果.Node(){};Node(int _set2[][maxn],int _loc,int _sum){for(int i=1;i<maxn;i++){for(int j=1;j<maxn;j++)set2[i][j]=_set2[i][j];}loc=_loc;sum=_sum;};friend operator <(Node a,Node b){return a.sum>b.sum;}
};
void solve(){priority_queue<Node>q;ans=1e7;for(int i=0;i<(1<<n);i++){int j=i;int sum=0;int vis2[maxn][maxn];memset(vis2,0,sizeof(vis2));for(int s=1;s<=n;s++){//枚举状态，你懂的qwqif(j&1<<(s-1)){if(vis2[i][s]==0)vis2[1][s]=1;if(vis2[1][s-1]==0)vis2[1][s-1]=2;if(vis2[1][s+1]==0)vis2[1][s+1]=2;if(vis2[2][s]==0)vis2[2][s]=2;sum++;}}int t=1;//bool ff=false;q.push(Node(vis2,t,sum));//优先队列}/*int vis2[maxn][maxn];memset(vis2,0,sizeof(vis2));vis2[1][3]=1;vis2[1][2]=2;vis2[1][4]=2;vis2[1][7]=1;vis2[1][6]=2;vis2[2][7]=2;vis2[2][3]=2;q.push(Node(vis2,1,2));*/while(!q.empty()){Node u=q.top();int loc=u.loc;q.pop();if(ans<=u.sum) continue;if(u.loc==m+1){bool flag=false;for(int i=1;i<=m&&!flag;i++){for(int j=1;j<=n&!flag;j++)if(u.set2[i][j]==0)flag=true;}if(flag) continue;if(ans>u.sum){ans=u.sum;for(int i=1;i<maxn;i++){for(int j=1;j<maxn;j++)ans2[i][j]=u.set2[i][j];}for(int i=1;i<=n;i++){if(ans2[m+1][i]==1){ans2[m][i]=1;ans++;}}}}int sum=0;int se2[maxn][maxn];memset(se2,0,sizeof(se2));for(int i=0;i<=m;i++){for(int j=0;j<maxn;j++)se2[i][j]=u.set2[i][j];}for(int i=1;i<=n;i++){if(se2[loc][i]==0){if(se2[loc][i]!=1)se2[loc][i]=2;if(se2[loc+1][i+1]!=1)se2[loc+1][i+1]=2;if(se2[loc+1][i-1]!=1)se2[loc+1][i-1]=2;if(se2[loc+1][i]!=1)se2[loc+1][i]=1;if(se2[loc+2][i]!=1)se2[loc+2][i]=2;sum++;}}q.push(Node(se2,u.loc+1,sum+u.sum));}
}
int main()
{     //freopen("e:\\solve\\tex1.txt","r",stdin);//freopen("e:\\solve\\tex3.txt","w",stdout);while(~scanf("%d%d",&m,&n)){if(m==0&&n==0)break;memset(ans2,0,sizeof(ans2));solve();cout<<ans<<endl;bool flag=false;/*for(int i=1;i<=m+1&&!flag;i++){for(int j=1;j<=n&&!flag;j++){cout<<ans2[i][j]<<" ";//cout<<endl;}cout<<endl;}*///cout<<"***"<<endl;if(!flag){for(int i=1;i<=m;i++){for(int j=1;j<=n;j++)if(ans2[i][j]==1){printf("1 ");}elseprintf("0 ");cout<<endl;}cout<<endl;}elseputs("-1");}return 0;
}

大佬的不重复代码。不想写了， 开心再写。（他这个也是错的，不信自己可以写数据对拍。2 5 输出
0 1 0 1 0
0 0 0 0 0 ，很多很多的。
）

#include <iostream>
#include <fstream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;const int MAX = 50;
int board[MAX][MAX];  //记录方格被监视情况
int root[MAX][MAX];      //记录机器人位置
int m, n;             //矩阵为 m * n
int k = 0;                //机器人个数
int bestk;void compute()
{memset(root, 0, sizeof(root));bool ok = false;int i, k;if(m == 1)  //矩阵只有一行的情况{k = n / 3;if(n%3 == 1){for(i=0; i<=k; i++)root[1][3*i+1] = 1;}else{if(n%3 == 0)k--;for(i=0; i<=k; i++)root[1][3*i+2] = 1;}bestk = k + 1;ok = true;}if(n == 1) //矩阵只有一列的情况{k = m / 3;if(m%3 == 1){for(i=0; i<=k; i++)root[1][3*i+1] = 1;}else{if(m%3 == 0)k--;for(i=0; i<=k; i++)root[1][3*i+2] = 1;}bestk = k + 1;ok = true;}if(m==2 && n%2 == 1) //矩阵有2行，且列数为奇数{int k = n / 4;if(m%4 == 0)k--;for(i=0; i<=k; i++){root[1][4*i+3] = 1;root[2][4*i+1] = 1;}bestk = 2 * k + 2;ok = true;}if(n==2 && m%2 == 1) //矩阵有2列，且行数为奇数{int k = m / 4;if(n%4 == 0)k--;for(i=0; i<=k; i++){root[1][4*i+3] = 1;root[2][4*i+1] = 1;}bestk = 2 * k + 2;ok = true;}if(n==4 && m==4)  //4行4列{root[1][1] = 1;root[1][4] = 1;root[4][1] = 1;root[4][4] = 1;bestk = 4;ok = true;}if(ok){//cout << "最少的机器人个数为：" << bestk << endl;//cout << "机器人位置为：\n";for(int i=1; i<=m; i++){for(int j=1; j<=n; j++)cout << root[i][j] << " ";cout << endl;}}elsecout << "-1\n";
}int main()
{//freopen("e:\\solve\\tex1.txt","r",stdin);//freopen("e:\\solve\\tex2.txt","w",stdout);//cout << "输入矩阵行数：";while(cin >> m>>n){//cout << "输入矩阵列数：";//cin >> n;compute();cout << endl;}return 0;
}

3 用二分图来解决的 可以重复坚守。（等我打完亚洲赛用网络流写。肯定写，不写是小狗）

#include <iostream>
using namespace std;#define MLEN 20int n, m, best, k=0, t=0, t1, t2, more;int d[6][3] = {{0,0,0},{0,0,0},{0,0,-1},{0,-1,0},{0,0,1},{0,1,0}};
int x[MLEN+1][MLEN+1];
int y[MLEN+1][MLEN+1];
int bestx[MLEN+1][MLEN+1];void change(int i, int j)
{x[i][j] = 1;k ++;for (int s=1; s<=5; s++){int p = i + d[s][1];int q = j + d[s][2];y[p][q] ++;if (y[p][q] == 1)t ++;}
}void restore(int i, int j)
{x[i][j] = 0;k --;for (int s=1; s<=5; s++){int p = i + d[s][1];int q = j + d[s][2];y[p][q] --;if (y[p][q] == 0)t --;}
}void search(int i, int j)
{do{j ++;if (j>m){i ++;j = 1;}}while(!(y[i][j]==0 || i>n));if (i>n){if (k<best){best = k;for (int p=1; p<=n; p++)for (int q=1; q<=m; q++){bestx[p][q] = x[p][q];}}return;}if (k+(t1-t)/5>=best){return;}//////////看不懂！///////////////////////////////if (i<n-1 && k+(t2-t)/5>=best){return;}
////////////////////////////////////////////////if (i<n){change (i+1, j);search (i, j);restore(i+1, j);}if (j<m && (y[i][j+1]==0 || y[i][j+2]==0)){change (i, j+1);search (i, j);restore(i, j+1);}if (y[i+1][j]==0 && y[i][j+1]==0){change (i, j);search (i, j);restore(i, j);}}void compute()
{int i;//////////看不懂！///////////////////////////////more = m/4 + 1;if (m%4 == 3)more ++;else if (m%4 == 2)more += 2;t2 = m*n + more +4;t1 = m*n +4;
/////////////////////////////////////////////////best = 65536;if (n==1 && m == 1){cout<<1<<endl;cout<<1<<endl;return;}for (i=0; i<=m+1; i++){y[0][i] = 1;y[n+1][i] = 1;}for (i=0; i<=n+1; i++){y[i][0] = 1;y[i][m+1] = 1;}search(1, 0);
}int main()
{while (cin>>n){cin>>m;k = 0;for (int i=0; i<=MLEN; i++){for (int j=0; j<=MLEN; j++){x[i][j] = 0;y[i][j] = 0;}}compute();cout<<best<<endl;for (int i=1; i<=n; i++){for (int j=1; j<=m; j++){cout<<bestx[i][j]<<" ";}cout<<endl;}}return 0;
}