本文节选自我的二分图学习笔记，欢迎来玩！
有一个长为 \(n\) 的字符串 \(s\)，只包含 \(\texttt a\dots\texttt f\) 共 \(6\) 种字符。你知道每种字符的出现次数，和每个位置可能出现哪些字符，你需要构造出满足条件且字典序最小的 \(s\)。
不难发现这是一个位置和字符之间的匹配问题，考虑建图网络流。
设字符 \(c\) 的出现次数为 \(\mathrm{cnt}_c\)。从源点 \(S\) 向每个位置 \(i\) 连容量为 \(1\) 的边，每个位置向这个位置可能出现的字符连容量为 \(1\) 的边，每个字符 \(c\) 向汇点 \(T\) 连容量为 \(\mathrm{cnt}_c\) 的边，跑最大流，如果能流满就有解，否则无解。
然而直接网络流难以找到字典序最小的匹配。网络流算法的流程很复杂，我们把握不住，所以尽量不要尝试改动网络流的板子，而是考虑其他方法。
最大 / 最小化字典序的问题都可以贪心。从前往后枚举位置 \(i\)，尽量让 \(i\) 放更小的字符。因此我们需要解决的问题转化为：当位置 \(i\) 流向字符 \(c\) 时，剩下的点还能否流满。
注意到如果不算源点和汇点，这就判断二分图是否有完美多重匹配（多重匹配：每个点 \(u\) 最多被 \(l_u\) 条边覆盖，而非一般匹配的 \(1\) 条边）。我们可以通过把每个点拆成 \(l_u\) 个点转化成一般匹配。我们称位置对应的点集为“位置部”，字符对应的点集为“字符部”。
此时我们需要引入 Hall 定理：
对于二分图 \(G=(A,B,E),|A|\le|B|\)，定义函数 \(f(S)\) \((S\subseteq A)\) 表示与 \(S\) 中的点有连边的点的数量，则 \(G\) 存在完美匹配的充要条件是 \(\forall S\subseteq A,f(S)\ge|S|\)。
我们显然不能枚举位置部的所有子集，但是字符部只有 \(6\) 个本质不同的点，相同的点无论放多少个，对 \(f\) 值都只会产生一个点的影响，所以只需要枚举 \(6\) 种字符的所有子集，只有 \(2^6=64\) 种情况。
对于每个 \(i\)，预处理出每个子集的后缀 \(f\) 值，即只考虑 \(i\) 到 \(n\) 这些位置时，每个子集的 \(f\) 值，然后贪心枚举即可。
设字符集为 \(\Sigma\)，则时间复杂度为 \(O(n|\Sigma|2^{|\Sigma|})\)。
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i, s, e) for(int i = s, i##E = e; i <= i##E; ++i)
#define per(i, s, e) for(int i = s, i##E = e; i >= i##E; --i)
#define F first
#define S second
// #define int ll
#define gmin(x, y) (x = min(x, y))
#define gmax(x, y) (x = max(x, y))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double f128;
typedef pair<int, int> pii;
constexpr int N = 1e5 + 5;
int n, t, cnt[6], sum[64], f[N][64];
bool ava[N][6];
string s;
signed main() {
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#endif
cin >> s; n = s.size();
for(auto c : s) cnt[c - 'a']++;
rep(i, 0, 63) rep(j, 0, 5) if(i >> j & 1) sum[i] += cnt[j];
cin >> t;
memset(ava, 1, sizeof ava);
rep(i, 1, t) {
int p; cin >> p >> s;
memset(ava[p], 0, sizeof ava[p]);
for(auto c : s) ava[p][c - 'a'] = 1;
}
per(i, n, 1) {
memcpy(f[i], f[i + 1], sizeof f[i]);
rep(j, 0, 63) rep(k, 0, 5)
if((j >> k & 1) && ava[i][k])
{ ++f[i][j]; break; }
}
s.clear();
rep(i, 1, n) {
bool flg = 0;
rep(j, 0, 5) if(ava[i][j]) {
bool fl = 1;
rep(k, 0, 63)
if(k >> j & 1) {
if(f[i + 1][k] < sum[k] - 1) { fl = 0; break; }
}
else if(f[i + 1][k] < sum[k]) { fl = 0; break; }
if(fl) {
flg = 1; s.push_back(j + 'a');
rep(k, 0, 63) if(k >> j & 1) --sum[k];
break;
}
}
if(!flg) cout << "Impossible\n", exit(0);
}
cout << s << endl;
return 0;
}