CF803E Roma and Poker 差分约束

CF803E Roma and Poker

记 W 为 \(1\)，L 为 \(-1\)，D 为 \(0\)，前 \(i\) 个字符的和为 \(dis_i\)。

则有：

• 当第 \(i\) 位为 W 时：

  \[dis_i-dis_{i-1}=1 \]

  可以推出：

  \[\begin{cases} dis_i-dis_{i-1}\le 1\\ dis_i-dis_{i-1}\ge 1\\ \end{cases} \]

  转为差分约束形式：

  \[\begin{cases} dis_i-dis_{i-1}\le 1\\ dis_{i-1}-dis_i\le -1\\ \end{cases} \]

  建边操作：

  add(i-1,i,1);
  add(i,i-1,-1);
  

• 当第 \(i\) 位为 L 时：

  \[\begin{cases} dis_i-dis_{i-1}\le -1\\ dis_{i-1}-dis_i\le 1\\ \end{cases} \]

  建边操作：

  add(i-1,i,-1);
  add(i,i-1,1);
  

• 当第 \(i\) 位为 D 时：

  \[\begin{cases} dis_i-dis_{i-1}\le 0\\ dis_{i-1}-dis_i\le 0\\ \end{cases} \]

  建边操作：

  add(i-1,i,0);
  add(i,i-1,0);
  

• 当第 \(i\) 位为 ? 时：

  \[\begin{cases} dis_i-dis_{i-1}\le 1\\ dis_{i-1}-dis_i\le 1\\ \end{cases} \]

  建边操作：

  add(i-1,i,1);
  add(i,i-1,1);
  

• 绝对值等于 \(k\)：

  有两种情况：

  \[\begin{cases} dis_n-dis_0\le k\\ dis_n-dis_0\ge k\\ \end{cases} \begin{cases} dis_n-dis_0\le -k\\ dis_n-dis_0\ge -k\\ \end{cases} \]

  改写：

  \[\begin{cases} dis_n-dis_0\le k\\ dis_0-dis_n\le -k\\ \end{cases} \begin{cases} dis_n-dis_0\le -k\\ dis_0-dis_n\le k\\ \end{cases} \]

  建边：

  add(n,0,-k);
  add(0,n,k);
  

  add(0,n,-k);
  add(n,0,k);
  

• 前缀的绝对值小于 \(k\)：

  \[\begin{cases} dis_i-dis_0\le k-1\\ dis_i-dis_0\ge -k+1\\ \end{cases} \]

  改写：

  \[\begin{cases} dis_i-dis_0\le k-1\\ dis_0-dis_i\le k-1\\ \end{cases} \]

  建边：

  add(0,i,k-1);
  add(i,0,k-1);
  

将以上条件全部建边，跑 SPFA 即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
char s[1010];
int dis[1010],cnt[1010];
bool vis[1010];
int tag1,tag2;
queue<int>q;
struct edge{
	int v,w,nxt;
}e[100010];
int head[1010],tot;
void add(int u,int v,int w){
	e[tot]={v,w,head[u]};
	head[u]=tot++;
}
bool spfa(int s){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	q.push(s);
	vis[s]=1,dis[s]=0;
	while(!q.empty()){
		int u=q.front();q.pop();
		vis[u]=0;
		for(int i=head[u];i!=-1;i=e[i].nxt){
			if(i==tag1||i==tag2)continue;
			int v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>n)return 0;
				if(!vis[v])q.push(v),vis[v]=1;
			}
		}
	}
	return 1;
}
int main(){
	memset(head,-1,sizeof(head));
	cin>>n>>k;
	scanf("%s",s+1);
	for(int i=1;i<=n;i++){
		if(s[i]=='W')add(i-1,i,1),add(i,i-1,-1);
		if(s[i]=='L')add(i-1,i,-1),add(i,i-1,1);
		if(s[i]=='D')add(i-1,i,0),add(i,i-1,0);
		if(s[i]=='?')add(i-1,i,1),add(i,i-1,1);
		if(i!=n)add(0,i,k-1),add(i,0,k-1);
	}
	add(n,0,-k),add(0,n,k);
	tag1=tag2=-1;
	if(spfa(0)){
		for(int i=1;i<=n;i++){
			switch(dis[i]-dis[i-1]){
				case 1:cout<<'W';break;
				case 0:cout<<'D';break;
				case -1:cout<<'L';break;
			}
		}
		return 0;
	}
	tag1=tot-1,tag2=tot-2;
	add(0,n,-k),add(n,0,k);
	if(spfa(0)){
		for(int i=1;i<=n;i++){
			switch(dis[i]-dis[i-1]){
				case 1:cout<<'W';break;
				case 0:cout<<'D';break;
				case -1:cout<<'L';break;
			}
		}
		return 0;
	}
	cout<<"NO";
	return 0;
}