题目链接
题意
你面前有一个数字锁，上面有 (d) 个按键，你按一下，按键就会被按下去，另外还有一个 Reset 键，按了以后之前所有被按下的键都会弹起来，当你按出了正确的密码，则锁会立刻打开。
现在你知道有 (n) 个可能的密码，请问至少需要按多少次按钮才能把所有密码都试一遍（按 Reset 也算一次）。
(1leq dleq 10)，(1leq nleq 2^d-1)
思路
建个图，如果密码 (i) 能通过另外按下一些键得到密码 (j)，则连一条 (i ightarrow 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) 神在线下吐槽，经过反省决定开始改成空格码风了。