Codeforces 1009G. Allowed Letters(贪心+网络流)

Author Avatar
Sakits 7月 22, 2018

题解

  这题还是挺套路的…就是很难调而已QAQ
  显然求字典序最小,应该从左到右贪心,那么问题就转化成了,考虑放下一个字符之后,剩下的字符能否组成合法的字符串。
  很容易发现是一个网络流模型,check的方法就是SS向每种字符连边,字符向262^6种位置连边,位置向TT连边,如果满流说明有解。那么放下一个字符之后,用网络流重新建图来check即可,但是复杂度较高。说不定dinic玄学可以过呢? 我也就想到这个地方就不会做了…我知道很显然每次不需要重新建图,但是想不出来怎么修改,大概是没见过这一类操作,其实应该也是不难想的…
  如果要在位置xx放下一个字符chch,那么实际上就是保证最大流里schxts-ch-x-t有一单位的流量来代表这个操作。
  如果已经有了,那么我们把这个流从图中删去表示钦定有这个流即可,也就是将sch,chx,xts-ch,ch-x,x-t的容量流量减去11,具体做法是将这些边的容量减去11反向边的剩余流量减去11(这里一开始没注意调了好久…)。
  如果这条路径流量为00,我们就要考虑强行给这条路径塞11单位流量之后能不能满流。也就是将sx,chts-x,ch-t的容量流量减去11,表示强行塞流量给这条路径,然后为了流量平衡,还需要在图中将sxs-x出发的一条流量不为00的路径和chtch-t结尾的一条流量不为00的路径回流11单位流量,此时再跑一次网络流,如果还能够增广,说明可以给schxts-ch-x-t这条路径塞流量,那么也就可行了。具体做法是将sx,chts-x,ch-t的容量减去11反向边的剩余流量减去11,再找从xx出发的一条路径和chch结尾的一条路径上的边11剩余流量+1+1,反向边剩余流量1-1,跑dinicdinic看看能否增广即可。
  如果不能增广,要还原被修改的边。
  增广的复杂度是O(n+m)O(n+m)的,主要复杂度在找流量不为00路径上,显然是可以跑得过的。
  PS:这题还有个更简单的做法,但是感觉我不会往那个方向想,而且网络流的做法要通用的多,所以就不展开写了。

题解

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int maxn=500010, inf=1e9;
struct edge{int too, c, cf, pre;}e[maxn];
int n, m, s, t, tot, x, y, z;
int last[73], d[73], h[73], cur[73], ep[233][233], st[maxn], cnt[maxn], cnt2[maxn];
vector<int>v;
char s1[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
}

inline void add(int x, int y, int z){e[++tot]=(edge){y, z, z, last[x]}; last[x]=tot;}

inline void ins(int x, int y, int z){add(x, y, z); ep[x][y]=tot; add(y, x, 0);}

inline bool bfs(int s, int t)
{
	for(int i=0;i<=t;i++) d[i]=-1; d[s]=0;
	int front=0, rear=1; h[1]=s;
	while(front!=rear)
	{
		int x=h[++front];
		for(int i=last[x], too;i;i=e[i].pre)
		if(e[i].cf && d[too=e[i].too]==-1) 
		{
			d[too]=d[x]+1, h[++rear]=too;
			if(too==t) return 1;
		}
	}
	return 0;
}

int dfs(int x, int t, int flow)
{
	if(x==t || !flow) return flow; 
	int f=0;
	for(int &i=cur[x], too;i;i=e[i].pre)
	if(e[i].cf && d[too=e[i].too]==d[x]+1)
	{
		int tmp=dfs(too, t, min(flow-f, e[i].cf));
		f+=tmp; e[i].cf-=tmp; e[i^1].cf+=tmp;
		if(flow==f) return f;
	}
	return f;
}

inline int dinic(int s, int t)
{
	int ans=0;
	while(bfs(s, t))
	{
		memcpy(cur, last, sizeof(last));
		ans+=dfs(s, t, inf);
	}
	return ans;
}	

inline bool change(int x, int ch)
{
	if(!(st[x] & (1<<(ch-1)))) return 0;
	int pos1=ep[s][ch], pos2=ep[ch][st[x]+7], pos3=ep[st[x]+7][t];
	if(e[pos1].c==e[pos1].cf || e[pos3].c==e[pos3].cf) return 0;
	if(e[pos2].c>e[pos2].cf) return e[pos1].c--, e[pos3].c--, e[pos2].c--, e[pos2^1].cf--, 1;
	v.clear(); e[pos1].c--; e[pos3].c--; e[pos1^1].cf--; e[pos3^1].cf--;
	for(int i=last[ch];i;i=e[i].pre)
	{
		if((i&1)==0 && e[i].c>e[i].cf)
		{
			v.push_back(i);
			e[i].cf++; e[i^1].cf--;
			for(int j=last[e[i].too];j;j=e[j].pre)
			{
				if((j&1)==0 && e[j].c>e[j].cf)
				{
					v.push_back(j); 
					e[j].cf++; e[j^1].cf--;
					break;
				}
			}
			break;
		}
	}
	for(int i=last[st[x]+7];i;i=e[i].pre)
	if((i&1) && e[i^1].c>e[i^1].cf)
	{
		v.push_back(i^1);
		e[i^1].cf++; e[i].cf--;
		for(int j=last[e[i].too];j;j=e[j].pre)
		if((j&1) && e[j^1].c>e[j^1].cf)
		{
			v.push_back(j^1); 
			e[j^1].cf++; e[j].cf--;
			break;
		}
		break;
	}
	if(dinic(s, t)) return 1;
	else
	{
		e[pos1].c++; e[pos3].c++; e[pos1^1].cf++; e[pos3^1].cf++;
		for(int i=0;i<v.size();i++)
		e[v[i]].cf--, e[v[i]^1].cf++;
		return 0;
	}
}

int main()
{
	scanf("%s", s1+1); n=strlen(s1+1); tot=1;
	for(int i=1;i<=n;i++) cnt[s1[i]-'a'+1]++;
	read(m);
	for(int i=1;i<=n;i++) st[i]=(1<<6)-1;
	for(int i=1;i<=m;i++)
	{
		read(x); scanf("%s", s1+1);
		int len=strlen(s1+1);
		st[x]=0;
		for(int j=1;j<=len;j++)
		st[x]|=(1<<(s1[j]-'a'));
	}
	s=0; t=7+(1<<6);
	for(int i=1;i<=6;i++) if(cnt[i]) ins(s, i, cnt[i]);
	for(int i=1;i<=n;i++) cnt2[st[i]]++;
	for(int i=0;i<(1<<6);i++) 
	if(cnt2[i])
	{
		ins(i+7, t, cnt2[i]);
		for(int j=1;j<=6;j++)
		if(i & (1<<(j-1))) ins(j, i+7, inf);
	}
	if(dinic(s, t)!=n) return puts("Impossible"), 0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=6;j++)
		if(change(i, j)) 
		{
			printf("%c", j+'a'-1);
			break;
		}
	}
}