中山市小榄新意网站设计有限公司,王老吉的品牌vi设计,网站建设与优化标准,生意街创业商机网Description 最近在生物实验室工作的小T遇到了大麻烦。 由于实验室最近升级的缘故#xff0c;他的分格实验皿是一个长方体,其尺寸为abc#xff0c;a、b、c 均为正整数。为了实验的方便#xff0c;它被划分为abc个单位立方体区域#xff0c;每个单位立方体尺寸 为111。用(i,…Description 最近在生物实验室工作的小T遇到了大麻烦。 由于实验室最近升级的缘故他的分格实验皿是一个长方体,其尺寸为abca、b、c 均为正整数。为了实验的方便它被划分为abc个单位立方体区域每个单位立方体尺寸 为111。用(i,j,k)标识一个单位立方体1 ≤i≤a1≤j≤b1≤k≤c。这个实验皿已经很久没有人用了现在小T被导师要求将其中一些单位立方体区域进 行消毒操作每个区域可以被重复消毒。而由于严格的实验要求他被要求使用一种特定 的F试剂来进行消毒。 这种F试剂特别奇怪每次对尺寸为xyz的长方体区域它由xyz个单位立方体组 成进行消毒时只需要使用min{x,y,z}单位的F试剂。F试剂的价格不菲这可难倒了小 T。现在请你告诉他最少要用多少单位的F试剂。(注min{x,y,z}表示x、y、z中的最小 者。) Input 第一行是一个正整数D表示数据组数。接下来是D组数据每组数据开头是三个数a,b,c表示实验皿的尺寸。接下来会出现a个b 行c列的用空格隔开的01矩阵0表示对应的单位立方体不要求消毒1表示对应的单位立方体需要消毒例如如果第1个01矩阵的第2行第3列为1则表示单位立方体(1,2,3)需要被消毒。输入保证满足abc≤5000,T≤3。 Output 仅包含D行每行一个整数表示对应实验皿最少要用多少单位 的F试剂。 Sample Input 1 4 4 4 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 Sample Output 3 HINT 对于区域(1,1,3)-(2,2,4)和(1,1,1)-(4,4,1)消毒分别花费2个单位和1个单位的F试剂。2017.5.26新加两组数据By Leoly未重测. Solution 洛谷的评测机有伟大的神力。。。。 对于这个题有一种鬼畜的伪证至于是什么不想说了。。。 首先我们可以证明我们一次一定是要消掉一个面的也就是消除的部分中的{x,y,z}里面一定有一个是1其他两个撑到最大因为这样可以保证最优。 那么我们现在可以继续看这道题了。首先考虑这样一个算法假设这个题目的要求变成在一个二维平面上搞那么明显我们把每行每列当做点把格子里是否有数变成边不难看出我们现在就是要求这个题的最小覆盖集那么没的说了一个最大流随便就过了。 然后我们开始考虑三维的明显的是没有三分图匹配这种鬼畜的算法那么怎么办呢 题目中有这样一个条件\(a\times b\times c\le 5000\)。随便开一下根可以发现这仨数里面肯定有一个比17要小那么就可以搞搞事情了我们可以把这个立方体最小的那条边当成高然后枚举删掉哪一层把没有删去的层拍扁到一个二维平面上那么就可以在这个新的二维平面上搞搞二分图匹配什么的了。 那么我们是不是就轻松A掉了这个题 Code1 #pragma comment(linker, /STACK:1024000000,1024000000)
#include iostream
#include cstdlib
#include cmath
#include string
#include cstring
#include cstdio
#include algorithm
#include queue
#include set
#define re register
#define max(a,b) ((a)(b)?(a):(b))
#define min(a,b) ((a)(b)?(a):(b))
#define pos(i,j,l) ((i-1)*b*c(j-1)*cl)
#define MAXN 5005
#define MAXM 15011
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(arr) memset(arr, 0, sizeof(arr))
const int inf 0x3f3f3f3f;
int n,s,t,cur[MAXN],m;
int d[5005],cut[20],a,b,c,cost,minn100,cnt;
int sx[4][5005];
struct po
{int nxt,to,w;
}edge[MAXM];
int head[MAXN],dep[MAXN],num-1;
inline int read()
{int x0,c1;char ch ;while((ch9||ch0)ch!-)chgetchar();while(ch-) c*-1,chgetchar();while(ch9ch0)xx*10ch-0,chgetchar();return x*c;
}
inline void add_edge(int from,int to,int w)
{edge[num].nxthead[from];edge[num].toto;edge[num].ww;head[from]num;
}
inline void add(int from,int to,int w)
{add_edge(from,to,w);add_edge(to,from,0);
}
inline bool bfs()
{for(re int is;it;i)dep[i]0;queueint q;while(!q.empty())q.pop();q.push(s);dep[s]1;while(!q.empty()){int uq.front();q.pop();for(re int ihead[u];i!-1;iedge[i].nxt){int vedge[i].to;if(dep[v]0edge[i].w0){dep[v]dep[u]1;if(vt) return 1;q.push(v);}}}return 0;
}
inline int dfs(int u,int dis)
{if(ut)return dis;int diss0;for(re int icur[u];i!-1;iedge[i].nxt){int vedge[i].to;if(edge[i].w!0dep[v]dep[u]1){int checkdfs(v,min(dis,edge[i].w));if(check!0){dis-check;disscheck;edge[i].w-check;edge[i^1].wcheck;if(dis0) break;}}}return diss;
}
inline int dinic()
{int ans0;while(bfs()){for(re int i0;it;i)cur[i]head[i];while(int ddfs(s,inf))ansd;}return ans;
}
inline void get_cut(int x)
{memset(cut,0,sizeof(cut));for(re int i0;ia;i){if(x(1i)) cut[i1]1,cost;}
}
inline void build()
{for(re int i1;ib;i)add(s,i,1);for(re int i1;ic;i)add(ib,t,1);
}
inline void prepare()
{for(re int is;it;i) head[i]-1;num-1;
}
inline void copy()
{for(re int i1;icnt;i)if(!cut[sx[1][i]])add(sx[2][i],sx[3][i]b,1);
}
int main()
{int Tread();while(T--){aread();bread();cread();int minxmin(a,min(b,c));memset(sx,0,sizeof(sx));cnt0;for(re int i1;ia;i)for(re int j1;jb;j)for(re int l1;lc;l){int xread();if(!x) continue;sx[1][cnt]i;sx[2][cnt]j;sx[3][cnt]l;}if(minxb) swap(a,b),swap(sx[1],sx[2]);else if(minxc) swap(a,c),swap(sx[1],sx[3]);s0,tbc1;for(re int i0;i1a;i){cost0;get_cut(i);if(costminn) continue;prepare();copy();build();costdinic();minnmin(minn,cost);}coutminnendl;minn100;}
}But 看到这个Code不同寻常了吧这个代码在洛谷上开着O2A掉了然后令人惊奇的是它过不了我自己手造的随机数据。。然后我把gay的比我快10倍的代码拿过来测了测照样过不了。。。。然后发现把图拍扁的时候这个效率有可能退化为\(a*b*c\)的鬼畜效率光这个就T掉了。。。。然后。。。看了下题解第一个发现是一遍DFS一遍重新构造图。。然后没有然后了。 Code2 额题解代码我自己的改来改去太丑了仔细看看那个搜索过程 #include cmath
#include cstdio
#include cstring
#include iostream
#include algorithm
using namespace std;
inline int read() {int res 0; bool bo 0; char c;while (((c getchar()) 0 || c 9) c ! -);if (c -) bo 1; else res c - 48;while ((c getchar()) 0 c 9)res (res 3) (res 1) (c - 48);return bo ? ~res 1 : res;
}
const int N 5005, E 23, INF 0x3f3f3f3f;
int n, D[5], pos, ecnt, nxt[N], adj[N], go[N], val[N], my[N],
X[N][5], Ans, cnt, vis[N], times;
bool sel[E];
void add_edge(int u, int v, int w) {nxt[ecnt] adj[u]; adj[u] ecnt; go[ecnt] v; val[ecnt] w;
}
bool dfs(int u) {for (int e adj[u], v; e; e nxt[e])if (!sel[val[e]] vis[v go[e]] times) {vis[v] times;if (!my[v] || dfs(my[v])) {my[v] u;return 1;}}return 0;
}
int solve(int tt) {int i, j, ans 0;for (i 1; i cnt; i) my[i] 0;for (i 1; i cnt; i) {times;if (dfs(i)) ans;if (tt ans Ans) return tt ans;}return tt ans;
}
void Dfs(int dep, int tt) {if (dep D[pos]) return (void) (Ans min(Ans, solve(tt)));sel[dep] 1; Dfs(dep 1, tt 1);sel[dep] 0; Dfs(dep 1, tt);
}
void work() {int i, j, k, x; n 0; Ans INF; cnt 0;pos 1; D[1] read(); D[2] read(); D[3] read();if (D[2] D[pos]) pos 2; if (D[3] D[pos]) pos 3;for (i 1; i 3; i) if (i ! pos) cnt max(cnt, D[i]);for (i 1; i D[1]; i) for (j 1; j D[2]; j)for (k 1; k D[3]; k) {x read(); if (x) X[n][1] i, X[n][2] j, X[n][3] k;}ecnt 0; for (i 1; i cnt; i) adj[i] 0;for (i 1; i n; i) {if (pos 1) add_edge(X[i][2], X[i][3], X[i][1]);else if (pos 2) add_edge(X[i][1], X[i][3], X[i][2]);else add_edge(X[i][1], X[i][2], X[i][3]);}printf(%d\n, (Dfs(1, 0), Ans));
}
int main() {int T read();while (T--) work();return 0;
} 转载于:https://www.cnblogs.com/victorique/p/9042473.html
