CF1288F Red-Blue Graph

Link

考虑上下界+费用流。

对于左部点\(u\)：

如果颜色为\(B\)，连\((s,u,[1,+\infty),0)\)。

如果颜色为\(R\)，连\((u,t,[1,+\infty),0)\)。

如果颜色为\(U\)，连\((s,u,+\infty,0),(u,t,+\infty,0)\)。

对于右部点\(u\)，我们将其颜色的\(R/B\)翻转然后类似于左部点建图即可。

对于所有原图中的边\((u,v)\)，连\((u,v,1,b)\)和\((v,u,1,r)\)。

然后跑最小费用可行流。

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

const int N=407,M=2407,inf=40001;

int s,t,tot=1,a[N],head[N],ver[M],next[M],edge[M],cost[M],flow[N],dis[N],inq[N],id[N];std::queue<int>q;char str[N];

int read(){int x;scanf("%d",&x);return x;}

void add(int u,int v,int f,int c)

{

    ver[++tot]=v,next[tot]=head[u],head[u]=tot,edge[tot]=f,cost[tot]=c;

    ver[++tot]=u,next[tot]=head[v],head[v]=tot,edge[tot]=0,cost[tot]=-c;

}

int spfa()

{

    memset(dis+1,0x3f,t<<2),q.push(s),inq[s]=1,dis[s]=0,flow[s]=inf,id[t]=-1;

    for(int i,u,v;!q.empty();)

    for(i=head[u=q.front()],q.pop(),inq[u]=0;i;i=next[i])

        if(edge[i]&&dis[v=ver[i]]>dis[u]+cost[i])

	    if(dis[v]=dis[u]+cost[i],id[v]=i,flow[v]=std::min(flow[u],edge[i]),!inq[v])

		q.push(v),inq[v]=1;

    return dis[t]<0;

}

int main()

{

    int n1=read(),n2=read(),m=read(),r=read(),b=read(),ans=0;

    s=n1+n2+1,t=s+1;

    scanf("%s",str+1);

    for(int i=1;i<=n1;++i)

	if(str[i]=='R') ans+=inf,add(i,t,1,-inf),add(i,t,inf,0);

	else if(str[i]=='B') ans+=inf,add(s,i,1,-inf),add(s,i,inf,0);

	else add(s,i,inf,0),add(i,t,inf,0);

    scanf("%s",str+1);

    for(int i=1;i<=n2;++i)

	if(str[i]=='B') ans+=inf,add(i+n1,t,1,-inf),add(i+n1,t,inf,0);

	else if(str[i]=='R') ans+=inf,add(s,i+n1,1,-inf),add(s,i+n1,inf,0);

	else add(s,i+n1,inf,0),add(i+n1,t,inf,0);

    for(int i=1,u,v;i<=m;++i) u=read(),v=read(),add(u,v+n1,1,b),add(v+n1,u,1,r);

    for(int p;spfa();) for(ans+=dis[t]*flow[t],p=t;p^s;p=ver[id[p]^1]) edge[id[p]]-=flow[t],edge[id[p]^1]+=flow[t];

    if(ans>=inf) return puts("-1"),0;

    printf("%d\n",ans);

    for(int i=1,st=4*(n1+n2)+1;i<=m;++i) putchar(edge[st+i*4-2]? 'B':edge[st+i*4]? 'R':'U');

}

巴特西

CF1288F Red-Blue Graph

最新文章

热门文章