WA on #11求助
查看原帖
WA on #11求助
528325
DHeasy楼主2025/7/24 13:01

dinic

#include<bits/stdc++.h>
#define ll long long
#define re register
#define fi first
#define se second
using namespace std;
inline ll read(){
	ll res=0ll,f=1;
	char c;
	for(;(c=getchar())<'0'||c>'9';c=='-'?f=-f:0);
	while(c>='0' && c<='9') res=(res<<1) + (res<<3) + c-'0',c=getchar();
	return res*f;
}
inline ll Max(re ll x,re ll y){return x>y?x:y;}
inline ll Min(re ll x,re ll y){return x<y?x:y;}
inline void cmax(re auto &x,re auto y){x=Max(x,y);}
inline void cmin(re auto &x,re auto y){x=Min(x,y);}
/*-----------------*/
const int N=1010;
const int M=10010;
const int inf=1e9;
int n,k,S,E,s[N],e_[N];ll ans;
int num=1,f[N],nxt[M],to[M],id[N],now[N];
ll w[M],e[M],t[M];
inline void add(re int a,re int b,re ll c,re ll d){
	// printf("%d %d %lld,%lld\n",a,b,c,d);
	to[++num]=b,w[num]=c,
	nxt[num]=f[a],f[a]=num,
	e[num]=d,t[num]=0;
}
inline void Add(re int a,re int b,re ll c,re ll d){
	add(a,b,c,d),add(b,a,-c,0);
}
ll dis[N],cnt[N];
bool vis[N];
queue<int> q;
inline bool spfa(){
	for(re int i=1;i<=n+3;i++)
		dis[i]=inf,cnt[i]=0,vis[i]=0;
	while(!q.empty()) q.pop();
	dis[n+2]=0,vis[n+2]=1,q.push(n+2);
	while(!q.empty()){
		int u=q.front();q.pop();
		vis[u]=0;
		for(re int i=f[u];i;i=nxt[i]){
			if(t[i]<e[i]&&dis[to[i]]>dis[u]+w[i]){
				dis[to[i]]=dis[u]+w[i];
				cnt[to[i]]=cnt[u]+1;
				if(cnt[to[i]]>=n) continue;
				if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return dis[n+1]!=inf;
}
ll sum;bool v[N];
inline ll dfs(re int u,re ll F){
	if(u==n+1) return F;
	ll nowf=0;v[u]=1;
	for(re int &i=now[u];i;i=nxt[i]){
		if(!v[to[i]]&&t[i]<e[i]&&dis[to[i]]==dis[u]+w[i]){
			ll nf=dfs(to[i],Min(F-nowf,e[i]-t[i]));
			if(!nf) continue;
			t[i]+=nf,t[i^1]-=nf;
			sum+=nf*w[i],nowf+=nf;
			if(nowf==F) return nowf;
		}
	}
	v[u]=0;
	return nowf;
}
inline void dinic(){
	while(spfa()){
		for(re int i=1;i<=n+3;i++)
			now[i]=f[i],v[i]=0;
		dfs(n+2,inf);
	}
}
int main(){
	n=read();k=read();S=read();E=read();
	for(re int i=1;i<=n;i++) s[i]=read();
	for(re int i=1;i<=n;i++) e_[i]=read();
	for(re int i=1;i<=n;i++) ans+=(ll)s[i];
	
	for(re int i=1;i<=n;i++)
		Add(i,Min(i+k,n+1),s[i]-e_[i],1);
	Add(n+2,n+3,0,k-S);
	for(re int i=1;i<=k;i++) Add(n+3,i,0,inf);
	for(re int i=1;i<=n;i++) Add(i,i+1,0,k-S-E);
	
	dinic(),ans-=sum;
	printf("%lld\n",ans);
	for(re int i=1;i<=n;i++)
		if(t[i<<1]<e[i<<1]) putchar('S');
		else putchar('E');
	return 0;
}
2025/7/24 13:01
加载中...