Codeforces 704D. Captain America(有源汇上下界最大流)

题解

  好久之前写的题,丢一下上下界最大流板子
  这题一眼行列连边就没了居然放在Div1 D题,可能是老外不是很会网络流…

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<map>
using namespace std;
const int maxn=500010, inf=1e9;
struct edge{int too, cf, pre;}e[maxn*30];
int n, m, s, t, ttt, tot, N, ans, x, y, z, r, b, tottx, totty, ss, tt, l, d;
int last[maxn], pos[maxn], cur[maxn], dist[maxn], h[maxn], cnt[maxn], deg[maxn], L[maxn], R[maxn], posx[maxn], posy[maxn];
map<int, int>mpx, mpy;

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, last[x]}; last[x]=tot;}

inline void ins(int x, int y, int z){add(x, y, z); add(y, x, 0);}

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

inline 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(dist[too=e[i].too]==dist[x]+1 && e[i].cf)
	{
		int tmp=dfs(too, t, min(flow-f, e[i].cf));
		e[i].cf-=tmp; e[i^1].cf+=tmp; f+=tmp;
		if(f==flow) break;
	}
	return f;
}

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

int main()
{
	tot=1; read(n); read(m); read(r); read(b); 
	for(int i=1;i<=n;i++)
	{
		read(x); read(y);
		if(!mpx[x]) mpx[x]=++tottx, posx[tottx]=x;
		if(!mpy[y]) mpy[y]=++totty, posy[totty]=y;
		int tx=mpx[x], ty=mpy[y];
		cnt[tx]++; cnt[ty+n]++; pos[++pos[0]]=tot+2;
		ins(tx, ty+n, 1);
	}
	s=0; t=totty+n+1; N=t; ss=++N; tt=++N;
	for(int i=1;i<=tottx;i++) L[i]=0, R[i]=inf;
	for(int i=1;i<=totty;i++) L[i+n]=0, R[i+n]=inf;
	for(int i=1;i<=m;i++)
	{
		read(ttt); read(l); read(d); 
		if(ttt==1) l=mpx[l]; else l=mpy[l]+n;
		if(d>=cnt[l]) continue;
		int nL=(cnt[l]-d+1)>>1, nR=(cnt[l]+d)>>1;
		if(nL>nR) return puts("-1"), 0;
		L[l]=max(L[l], nL), R[l]=min(R[l], nR);
	}
	for(int i=1;i<=tottx;i++) deg[s]-=L[i], deg[i]+=L[i], ins(s, i, R[i]-L[i]);
	for(int i=1;i<=totty;i++) deg[i+n]-=L[i+n], deg[t]+=L[i+n], ins(i+n, t, R[i+n]-L[i+n]);
	for(int i=0;i<=N;i++) if(deg[i]>0) ins(ss, i, deg[i]);
	else if(deg[i]<0) ins(i, tt, -deg[i]);
	ins(t, s, inf); dinic(ss, tt); ans=0;
	for(int i=last[ss];i;i=e[i].pre) if(e[i].cf) return puts("-1"), 0;
	ins(t, s, -inf); dinic(s, t); printf("%I64d\n", 1ll*max(r, b)*n-1ll*(max(r, b)-min(r, b))*ans);
	for(int i=1;i<=pos[0];i++) printf("%s", (e[pos[i]].cf)?(r<b?"r":"b"):(r>b?"r":"b"));
}