题解 CF1009G 【Allowed Letters】
xtx1092515503
·
·
题解
CF官方题解思路I：
凡是字典序最小的东西都可以贪心，因为只要保证当前位填出的东西尽量大，后面的位都只要保证有个解就行了。比如这道题，就是枚举每一位填什么，然后用网络流判断出后面有无合法解。
我们顺序枚举每一位填什么。我们建出6个点代表'a'到'f'字符，同时将每位可以填的字符种类状压一下，状压出2^6个点。每个字符向所有包含着它的状态连一条无穷大的边，源点向每个字符连“剩余部分该字符出现次数”边权的边，同时每个bitmask向汇点连“剩余部分该bitmask出现次数”边权的边。这就是相当于用6个字符与2^6个bitmask进行二分图多重匹配。
这样，如果跑出来的最大流等于“剩余部分长度”，则当前位填入该字符是合法的。
如果我们就这么直接每次都跑一遍网络流的话，复杂度最差为
代入$n={3*10}^5,A=6$，得复杂度最劣为${3*10}^5*6*{70}^2*192\approx1.7*{10}^{12}$。因为网络流复杂度玄学，不妨乘上一个百分之一的常数，得复杂度约为$1.7*{10}^{10}$，不可能通过本题。
以下是这个TLE的暴力网络流代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int lim=1<<6;
int n,mask[100100],m,tot[lim],cmp[6];
char s[100100],ss[6],ans[100100];
namespace MaxFlow{
const int N=10000,M=200000;
int head[N],cur[N],dep[N],cnt,S,T,res;
struct node{
int to,next,val;
}edge[M];
void ae(int u,int v,int w){
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
}
queue<int>q;
inline bool bfs(){
memset(dep,0,sizeof(dep)),q.push(S),dep[S]=1;
while(!q.empty()){
register int x=q.front();q.pop();
for(register int i=cur[x]=head[x];i!=-1;i=edge[i].next)if(edge[i].val&&!dep[edge[i].to])dep[edge[i].to]=dep[x]+1,q.push(edge[i].to);
}
return dep[T]>0;
}
bool reach;
inline int dfs(int x,int flow){
if(x==T){
res+=flow;
reach=true;
return flow;
}
int used=0;
for(register int &i=cur[x];i!=-1;i=edge[i].next){
if(!edge[i].val||dep[edge[i].to]!=dep[x]+1)continue;
register int ff=dfs(edge[i].to,min(edge[i].val,flow-used));
if(ff){
edge[i].val-=ff;
edge[i^1].val+=ff;
used+=ff;
if(used==flow)break;
}
}
return used;
}
inline void Dinic(){
while(bfs()){
reach=true;
while(reach)reach=false,dfs(S,0x3f3f3f3f);
}
}
}
using namespace MaxFlow;
int che(){
for(register int i=head[S];i!=-1;i=edge[i].next)edge[i].val=cmp[edge[i].to],edge[i^1].val=0;
for(register int i=head[T];i!=-1;i=edge[i].next)edge[i^1].val=tot[edge[i].to-6],edge[i].val=0;
res=0;
Dinic();
return res;
}
inline void read(int &x){
x=0;
register char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x){
if(x<=9)putchar('0'+x);
else print(x/10),putchar('0'+x%10);
}
int main(){
scanf("%s",s+1),n=strlen(s+1),S=6+lim,T=6+lim+1;
for(register int i=1;i<=n;i++)cmp[s[i]-'a']++;
read(m);
for(register int i=1,x,y;i<=m;i++){
read(x),scanf("%s",ss),y=strlen(ss);
for(register int j=0;j<y;j++)mask[x]|=1<<(ss[j]-'a');
}
for(register int i=1;i<=n;i++)if(!mask[i])mask[i]=lim-1;
for(register int i=1;i<=n;i++)tot[mask[i]]++;
memset(head,-1,sizeof(head));
for(register int i=0;i<6;i++)ae(S,i,cmp[i]);
for(register int i=0;i<lim;i++)for(register int j=0;j<6;j++)if(i&(1<<j))ae(j,i+6,0x3f3f3f3f);
for(register int i=0;i<lim;i++)ae(i+6,T,tot[i]);
Dinic();
if(res!=n){puts("Impossible");return 0;}
for(register int i=1;i<=n;i++)for(register int j=0;j<6;j++){
if(!(mask[i]&(1<<j)))continue;
if(!cmp[j])continue;
tot[mask[i]]--,cmp[j]--;
if(che()!=n-i)tot[mask[i]]++,cmp[j]++;
else{ans[i]='a'+j;break;}
}
ans[n+1]='\0';
printf("%s",ans+1);
return 0;
}
```
网络流题最有效的优化是什么？**残量网络优化**。在重跑网络流时，不再全体清空边权，而是只清空少量边权，其它部分仍沿用之前结果。
我们考虑当尝试在一个bitmask为$msk$的位置上填入字符$chr$的变化：
首先，我们找出边$(S,chr)$和$(msk,T)$。显然，这两条边必须是满流量的（不然最大流肯定不为$n$）。
我习惯**只记录边的残量**。因此，我们可以观察它们的反边，则反边上的残量即为当前正边上的流量，也就是正边上的流量上限（最大流必定满流）。如果反边残量为0，就意味着正边流量为$0$，就意味着正边流量上限为$0$，就意味着$chr$或$msk$已经一个不剩了，因此肯定是不合法的，直接跳掉。
如果边$(chr,msk)$上流量不为零（即反边有残量），则我们完全可以直接使这条边上流量减一，直接判为合法并退出。
否则，我们找到一条新的增广路$(S\rightarrow 1\rightarrow x\rightarrow T)$，其中这个$x$可以是任何节点。当然，这里面任何一条边，都必须有流量（而不是常规增广路的定义 **“未满流的路径”** ，因为这条增广路是为退流而用）。
当我们找到这样一条增广路后（必然存在，因为边$(S,chr)$出来的流量最终肯定流向汇点），就把增广路上每一条边的流量全都减少一（即反边残量减一，正边残量加一）。
同时，我们从$msk$出发，找一条反向的增广路，道理还是退流，只不过这里找的就是常规增广路（未满流的路径），因为这回的退流就是反边残量加一，正边残量减一。
全都做完以后，删去边$(S,chr)$与$(msk,T)$的各一点流量，因为这次匹配后，$chr$和$msk$的出现次数将会各减少1，固然是需要删去的。
这么一番操作后，我们成功拆掉了两点流量（正增广路的一点，反增广路的一点）。然后，我们再要跑最大流验证不小心多拆的那一点（即边$(chr,msk)$上原应有的那一点）能不能补回来。如果可以，那这次匹配就算成功了，直接退出。否则，匹配失败，去掉两条增广路的所有影响，返回匹配失败。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int lim=1<<6;
int n,mask[100100],m,tot[lim],cmp[6],enm[80][80];
char s[100100],ss[6];
namespace MaxFlow{
const int N=10000,M=200000;
int head[N],cur[N],dep[N],cnt,S,T,res;
struct node{
int to,next,val;
}edge[M];
void ae(int u,int v,int w){
enm[u][v]=cnt,edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
enm[v][u]=cnt,edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
}
queue<int>q;
inline bool bfs(){
memset(dep,0,sizeof(dep)),q.push(S),dep[S]=1;
while(!q.empty()){
register int x=q.front();q.pop();
for(register int i=cur[x]=head[x];i!=-1;i=edge[i].next)if(edge[i].val&&!dep[edge[i].to])dep[edge[i].to]=dep[x]+1,q.push(edge[i].to);
}
return dep[T]>0;
}
bool reach;
inline int dfs(int x,int flow){
if(x==T){
res+=flow;
reach=true;
return flow;
}
int used=0;
for(register int &i=cur[x];i!=-1;i=edge[i].next){
if(!edge[i].val||dep[edge[i].to]!=dep[x]+1)continue;
register int ff=dfs(edge[i].to,min(edge[i].val,flow-used));
if(ff){
edge[i].val-=ff;
edge[i^1].val+=ff;
used+=ff;
if(used==flow)break;
}
}
return used;
}
inline void Dinic(){
while(bfs()){
reach=true;
while(reach)reach=false,dfs(S,0x3f3f3f3f);
}
}
}
using namespace MaxFlow;
inline void read(int &x){
x=0;
register char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x){
if(x<=9)putchar('0'+x);
else print(x/10),putchar('0'+x%10);
}
bool fillin(int msk,int cha){
if(!(msk&(1<<cha)))return false;
int p1=cha,p2=msk+6;
int e1=enm[S][p1],e2=enm[p2][T];
if(!edge[e1^1].val||!edge[e2^1].val)return false;
edge[e1^1].val--;
edge[e1].val++;
vector<int>afe;
afe.push_back(e1);
for(int i=head[p1],x;i!=-1;i=edge[i].next){
if((i&1)||!edge[i^1].val)continue;
afe.push_back(i);
edge[i^1].val--;
edge[i].val++;
x=edge[i].to;
for(int j=head[x];j!=-1;j=edge[j].next){
if(j&1)continue;
afe.push_back(j);
edge[j^1].val--;
edge[j].val++;
break;
}
break;
}
if(edge[e2].val){edge[e2].val--,edge[e1].val--;return true;}
afe.push_back(e2);
edge[e2^1].val--;
edge[e2].val++;
for(int i=head[p2],x;i!=-1;i=edge[i].next){
if(!(i&1)||!edge[i].val)continue;
afe.push_back(i^1);
edge[i^1].val++;
edge[i].val--;
x=edge[i].to;
for(int j=head[x];j!=-1;j=edge[j].next){
if(!(j&1))continue;
afe.push_back(j^1);
edge[j^1].val++;
edge[j].val--;
break;
}
break;
}
edge[e1].val--;
edge[e2].val--;
res=0;
Dinic();
if(res)return true;
edge[e1].val++;
edge[e2].val++;
for(int i=0;i<afe.size();i++)edge[afe[i]].val--,edge[afe[i]^1].val++;
return false;
}
int main(){
scanf("%s",s+1),n=strlen(s+1),S=6+lim,T=6+lim+1;
for(register int i=1;i<=n;i++)cmp[s[i]-'a']++;
read(m);
for(register int i=1,x,y;i<=m;i++){
read(x),scanf("%s",ss),y=strlen(ss);
for(register int j=0;j<y;j++)mask[x]|=1<<(ss[j]-'a');
}
for(register int i=1;i<=n;i++)if(!mask[i])mask[i]=lim-1;
for(register int i=1;i<=n;i++)tot[mask[i]]++;
memset(head,-1,sizeof(head));
for(register int i=0;i<6;i++)ae(S,i,cmp[i]);
for(register int i=0;i<lim;i++)for(register int j=0;j<6;j++)if(i&(1<<j))ae(j,i+6,0x3f3f3f3f);
for(register int i=0;i<lim;i++)ae(i+6,T,tot[i]);
Dinic();
if(res!=n){puts("Impossible");return 0;}
for(register int i=1;i<=n;i++)for(register int j=0;j<6;j++)if(fillin(mask[i],j)){putchar('a'+j);break;}
return 0;
}
```
CF官方题解思路II：有个叫做Hall's theorem的奇怪玩意，我也不会用……