土石方工程网站,郑州模板网站建设,跨境电商创业新手怎么做,公众平台 wordpress文章目录题目描述解析代码题目描述
最近在生物实验室工作的小 T 遇到了大麻烦。 由于实验室最近升级的缘故#xff0c;他的分格实验皿是一个长方体#xff0c;其尺寸为 a∗b∗ca*b*ca∗b∗c。为了实验的方便#xff0c;它被划分为 a∗b∗ca*b*ca∗b∗c 个单位立方体区域他的分格实验皿是一个长方体其尺寸为 a∗b∗ca*b*ca∗b∗c。为了实验的方便它被划分为 a∗b∗ca*b*ca∗b∗c 个单位立方体区域每个单位立方体尺寸为 1∗1∗11*1*11∗1∗1并用 (i,j,k)(i,j,k)(i,j,k) 标识一个单位立方体。这个实验皿已经很久没有人用了。现在小 T 被导师要求将其中一些单位立方体区域进行消毒操作每个区域可以被重复消毒。
而由于严格的实验要求他被要求使用一种特定的 F 试剂来进行消毒。 这种 F 试剂特别奇怪每次对尺寸为 x∗y∗zx*y*zx∗y∗z 的长方体区域它由 x∗y∗zx*y*zx∗y∗z 个单位立方体组成进行消毒时只需要使用 min(x,y,z)min(x,y,z)min(x,y,z) 单位的 F 试剂。F 试剂的价格不菲这可难倒了小 T。
现在请你告诉他最少要用多少单位的 F 试剂。
解析 非暴力不合作 首先可以有一个结论**每次使min(x,y,z)1min(x,y,z)1min(x,y,z)1,一定是不劣的 所以我们就每次一面一面的涂 看一个《弱化版》的题目 在一N∗NN*NN∗N个 的矩阵中有 KKK个格子中有杂物现在你有一种能力一次可以消除一行或一列格子中的杂物问你至少需要几次可以将这些杂物全部消完。 这题应该是二分图的入门题了把每个点的x坐标与y坐标相连跑二分图最大匹配即可 不难发现消毒这题应该就是消除杂物的升级版从二维变成了三维 然鹅很快我们就发现并不能推广到k维。。。 当然如果您能发明三分图匹配本题就和喝水一样 那么我们怎么办呢 然后就点开了题解 还是暴力的思想了 考虑到数据范围 a∗b∗c5000a*b*c5000a∗b∗c5000
那么a、b、c中的最小值应该不超过17 所以我们考虑暴力枚举最小的一维的选取状态然后每次跑一遍匈牙利取答案最小值即可
另外本题还有一个很巧妙的实现技巧 先把坐标存到三个一维数组里 把最小的一维swap到a的位置同时把对应的那一位的数组swap到第一位 代码实现就变得很简单了
代码
#includebits/stdc.h
using namespace std;
const int N5020;
#define ll long long
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();};return x*f;
}
int n,m,l;
struct node{int from,to,nxt;
}p[N];
int fi[N],cnt-1;
void addline(int x,int y){p[cnt](node){x,y,fi[x]};fi[x]cnt;
}
int vis[N],mat[N];
bool dfs(int x,int tim){if(vis[x]tim) return false;vis[x]tim;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(!mat[to]||dfs(mat[to],tim)){mat[to]x;return true;}}return false;
}
int a,b,c;
int hungary(){int res0;memset(vis,0,sizeof(vis));memset(mat,0,sizeof(mat));for(int i1;ib;i){if(dfs(i,i)){res;//printf( ok:%d\n,i);}}return res;
}int q[4][N],num;
bool ok[35];
int ans;
int calc(){memset(fi,-1,sizeof(fi));cnt-1;for(int i1;inum;i){if(ok[q[1][i]]) continue;int xq[2][i],yq[3][i];addline(x,yb);addline(yb,x);// printf(x%d y%d\n,x,y);}return hungary();
}
void find(int k,int val){if(ka){//printf(ok);//printf(-------------val%d\n,val);//for(int i1;ia;i) printf(%d ,ok[i]);//printf(\n);ansmin(ans,calc()val);//printf(---ans%d\n\n,ans);return;}find(k1,val);ok[k]1;find(k1,val1);ok[k]0;
}
int main(){int Tread();while(T--){aread();bread();cread();num0;ans5000;int mnmin(a,min(b,c));for(int i1;ia;i){for(int j1;jb;j){for(int k1;kc;k){int xread();if(!x) continue;q[1][num]i;q[2][num]j;q[3][num]k;}}}if(mnb){swap(a,b);swap(q[1],q[2]);}else if(mnc){swap(a,c);swap(q[1],q[3]);}find(1,0);printf(%d\n,ans);}return 0;
}
/**/
