你面前有一个数字锁，上面有 \(d\) 个按键，你按一下，按键就会被按下去，另外还有一个 Reset 键，按了以后之前所有被按下的键都会弹起来，当你按出了正确的密码，则锁会立刻打开。
现在你知道有 \(n\) 个可能的密码，请问至少需要按多少次按钮才能把所有密码都试一遍（按 Reset 也算一次）。
\(1\leq d\leq 10\)，\(1\leq n\leq 2^d-1\)
思路建个图，如果密码 \(i\) 能通过另外按下一些键得到密码 \(j\)，则连一条 \(i\rightarrow j\) 的有向边，可以发现原题转化成了类似于有向图最小可重复点路径覆盖的问题，不同之处在于这里每条路径是带权的，权值为路径终点代表的那个密码包含的按下的键个数（密码的输入形式是 \(01\) 串，下来就直接说是 \(1\) 的个数了）。
这个看起来是能贪心的，先考虑跑匈牙利，首先最优解肯定是拆点二分图的一个最大匹配，那我们对点按照 \(1\) 的个数排序，从大到小一个个匹配，由于若一个点能被匹配，那它必然存在于最优解的方案中，从而这么做是正确的。
但是 \(O(NM)\) 的时间复杂度看起来不大能过，想想用 \(Dinic\) 网络流怎么做，因为 \(Dinic\) 一次是匹配多条增广路，然后再更新残余网络，所以原本我们需要的最佳顺序可能会被打乱，而最佳顺序跑不出新的增广路，于是不会更新方案，事实上你会在 \(CF\) 上 Wrong answer on test 23。
既然这样不正确，经过一定的思考（手玩对拍的数据）能够发现，其实我们直接强制匹配顺序就可以了，先根据 \(1\) 的数量对点进行分层，之后从大往小一层层地加入点，每加一层跑一遍 \(Dicnic\)，层之间的点对答案的贡献没有区别，从而这道题就被解决了。
分析一下复杂度，边（即子集关系）的数量级是 \(O(3^d)\) 的，而 \(n\) 是 \(O(2^d)\) 级别的，所以时间复杂度是 \(O(3^d2^\frac{d}{2})\)，同时还可以发现，原来跑匈牙利的时间复杂度只有 \(O(6^d)\)，已经足够通过本题了。
Code我是傻子，没发现匈牙利能过，调半天写了 \(Dinic\)，不过速度确实比 \(Hungary\) 要快一点。
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<vector> #define mem(a,b) memset(a,b,sizeof(a)) #define rep(i,a,b) for(int i = (a); i <= (b); i++) #define per(i,b,a) for(int i = (b); i >= (a); i--) #define N 2100 #define M 210000 #define Inf 0x3f3f3f3f using namespace std; int n, d; int num[N]; int head[N], to[M], nxt[M]; int cap[M], now[N], dis[N], pre[N]; int cnt; queue<int> q; vector<int> layers[12]; void init(){mem(head, -1), cnt = -1;} void add_e(int a, int b){ nxt[++cnt] = head[a], head[a] = cnt, to[cnt] = b; nxt[++cnt] = head[b], head[b] = cnt, to[cnt] = a; cap[cnt] = 0, cap[cnt^1] = 1; } bool bfs(){ mem(dis, 0); q.push(0), dis[0] = 1; while(q.size()){ int cur = q.front(); q.pop(); now[cur] = head[cur]; for(int i = head[cur]; ~i; i = nxt[i]){ if(cap[i] && !dis[to[i]]){ q.push(to[i]); dis[to[i]] = dis[cur]+1; } } } return dis[2*n+1]; } int dfs(int x, int flow){ if(x == 2*n+1) return flow; int flown = 0, i; for(i = now[x]; ~i; i=nxt[i]){ now[x] = i; int y = to[i]; if(cap[i] && dis[y] == dis[x]+1){ int t = dfs(y, min(flow-flown, cap[i])); cap[i] -= t, cap[i^1] += t; if(t) pre[x] = y; flown += t; if(flown == flow) break; } } return flown; } int main(){ ios::sync_with_stdio(false); cin>>d>>n; string s; rep(i,1,n){ cin>>s; per(j,d-1,0) num[i] = (num[i]*2+(s[j] == \'1\')); layers[__builtin_popcount(num[i])].push_back(i); } init(); rep(i,1,n){ add_e(0, i); add_e(i+n, 2*n+1); } per(stage,d,1){ rep(frt,stage+1,d){ for(int x:layers[stage]) for(int y:layers[frt]) if((num[x]&num[y]) == num[x]) add_e(x, y+n); } while(bfs()) while(dfs(0, Inf)); } vector<int> ans; pre[0]=0; rep(stage,1,d) for(int i:layers[stage]){ if(pre[i] == -1) continue; int t = i; ans.push_back(-1); rep(j,0,d-1) if(num[i]>>j&1) ans.push_back(j); while(pre[t]){ int k = pre[t]-n; int diff = num[t]^num[k]; rep(j,0,d-1) if(diff>>j&1) ans.push_back(j); pre[t] = -1; t = k; } pre[t] = -1; } cout<<(int)ans.size()-1<<endl; rep(i,1,(int)ans.size()-1){ if(~ans[i]) cout<<ans[i]<<" "; else cout<<"R "; } cout<<endl; return 0; }题外话：前两天码风被 \(zjc\) 神在线下吐槽，经过反省决定开始改成空格码风了。