[Hnoi2013]消毒

Description

最近在生物實驗室工作的小T遇到了大麻煩。
由于實驗室最近升級的緣故，他的分格實驗皿是一個長方體,其尺寸為abc，a、b、c 均為正整數。為了實驗的方便，它被劃分為abc個單位立方體區域，每個單位立方體尺寸
為111。用(i,j,k)標識一個單位立方體，1 ≤i≤a，1≤j≤b，1≤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

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)*c+l)
#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,minn=100,cnt;
int sx[4][5005];
struct po
{int nxt,to,w;
}edge[MAXM];
int head[MAXN],dep[MAXN],num=-1;
inline int read()
{int x=0,c=1;char ch=' ';while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();while(ch=='-') c*=-1,ch=getchar();while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();return x*c;
}
inline void add_edge(int from,int to,int w)
{edge[++num].nxt=head[from];edge[num].to=to;edge[num].w=w;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 i=s;i<=t;i++)dep[i]=0;queue<int> q;while(!q.empty())q.pop();q.push(s);dep[s]=1;while(!q.empty()){int u=q.front();q.pop();for(re int i=head[u];i!=-1;i=edge[i].nxt){int v=edge[i].to;if(dep[v]==0&&edge[i].w>0){dep[v]=dep[u]+1;if(v==t) return 1;q.push(v);}}}return 0;
}
inline int dfs(int u,int dis)
{if(u==t)return dis;int diss=0;for(re int& i=cur[u];i!=-1;i=edge[i].nxt){int v=edge[i].to;if(edge[i].w!=0&&dep[v]==dep[u]+1){int check=dfs(v,min(dis,edge[i].w));if(check!=0){dis-=check;diss+=check;edge[i].w-=check;edge[i^1].w+=check;if(dis==0) break;}}}return diss;
}
inline int dinic()
{int ans=0;while(bfs()){for(re int i=0;i<=t;i++)cur[i]=head[i];while(int d=dfs(s,inf))ans+=d;}return ans;
}
inline void get_cut(int x)
{memset(cut,0,sizeof(cut));for(re int i=0;i<a;i++){if(x&(1<<i)) cut[i+1]=1,cost++;}
}
inline void build()
{for(re int i=1;i<=b;i++)add(s,i,1);for(re int i=1;i<=c;i++)add(i+b,t,1);
}
inline void prepare()
{for(re int i=s;i<=t;i++) head[i]=-1;num=-1;
}
inline void copy()
{for(re int i=1;i<=cnt;i++)if(!cut[sx[1][i]])add(sx[2][i],sx[3][i]+b,1);
}
int main()
{int T=read();while(T--){a=read();b=read();c=read();int minx=min(a,min(b,c));memset(sx,0,sizeof(sx));cnt=0;for(re int i=1;i<=a;i++)for(re int j=1;j<=b;j++)for(re int l=1;l<=c;l++){int x=read();if(!x) continue;sx[1][++cnt]=i;sx[2][cnt]=j;sx[3][cnt]=l;}if(minx==b) swap(a,b),swap(sx[1],sx[2]);else if(minx==c) swap(a,c),swap(sx[1],sx[3]);s=0,t=b+c+1;for(re int i=0;i<1<<a;i++){cost=0;get_cut(i);if(cost>minn) continue;prepare();copy();build();cost+=dinic();minn=min(minn,cost);}cout<<minn<<endl;minn=100;}
}

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