题目链接
https://atcoder.jp/contests/agc031/tasks/agc031_e
题解
这是我yy出来的一个上下界费用流做法，网上没找到一样的做法，如果有什么问题敬请指出，谢谢。（一开始一直WA以为做法假了结果发现写错了一个sb地方摔）
考虑一维怎么做，首先可以枚举一共选多少个，那么对每个位置的限制就相当于“前(i)个里选的个数在([L_i,R_i])之间”。
我们可以给每个位置建一个点，源点往(1)号位置的点连(([0,+infty],0)), (i)往((i+1))连(([L_i,R_i],0)), (i)往汇点连(([0,1],w_i)), 跑最大费用最大流即可。
然后拓展到二维：我们给每一行每一列分别建一个点，记作(R_i,C_j). 对每个物品(u), 从(R_{x_u})往(C_{y_u})连(([0,1],w_u)). 设限制形如“从第(i)行到最后一行选的个数在([LX_i,RX_i])之间”、“前(j)列选的个数在([LY_j,RY_j])之间”，则从(R_{i-1})向(R_i)连(([LX_i,RX_i],0)) (特别地，(i=0)时起点为源点)，从(C_j)向(C_{j+1})连(([LY_j,RY_j],0)) (特别地，(j=MX)时终点为汇点,(MX)为最大坐标)，跑最大费用流就可以了。
这里上下界网络流因为最大流已知，我采用的是把每条边的下界费用设为无穷大的写法，需要使用__int128. 有其他的写法但是博主太菜了不会……
时间复杂度(O(ncdot MFMC(2n,5n))). (一共要建(3n)条边，其中至多(2n)条带上下界)
代码
做法一
#include<bits/stdc++.h>
#define llong long long
#define mkpr make_pair
#define pii pair<int,int>
#define riterator reverse_iterator
using namespace std;
inline int read()
{
int x = 0,f = 1; char ch = getchar();
for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
return x*f;
}
namespace NetFlow
{
const int N = 206;
const int M = 284;
#define lllong __int128
const lllong INF = 2e17;
const lllong INF2 = 1e22;
struct AEdge
{
int u,v,wl,wr; lllong c;
} ae[M+3];
struct Edge
{
int u,v,nxt,w; lllong c;
} e[(M<<2)+3];
int fe[N+3];
lllong dis[N+3];
int que[N+5];
bool inq[N+3];
int lst[N+3];
int n,m,en,s,t; lllong mf,mc;
void init()
{
memset(ae,0,sizeof(ae)); memset(e,0,sizeof(e)); memset(fe,0,sizeof(fe)); memset(dis,0,sizeof(dis)); memset(que,0,sizeof(que)); memset(inq,0,sizeof(inq)); memset(lst,0,sizeof(lst));
n = m = s = t = 0; mf = mc = (lllong)0;
}
void addedge0(int u,int v,int w,lllong c)
{
en++; e[en].u = u,e[en].v = v,e[en].w = w,e[en].c = c;
e[en].nxt = fe[u]; fe[u] = en;
en++; e[en].u = v,e[en].v = u,e[en].w = 0,e[en].c = -c;
e[en].nxt = fe[v]; fe[v] = en;
}
bool spfa()
{
for(int i=1; i<=n; i++) dis[i] = -INF2;
int hd = 1,tl = 2; que[1] = s; dis[1] = 0;
while(hd!=tl)
{
int u = que[hd]; hd++; if(hd>n+1) hd-=n+1;
for(int i=fe[u]; i; i=e[i].nxt)
{
int v = e[i].v;
if(e[i].w>0&&dis[e[i].v]<dis[u]+e[i].c)
{
dis[e[i].v] = dis[u]+e[i].c; lst[e[i].v] = i;
if(!inq[e[i].v])
{
inq[e[i].v] = true;
que[tl] = e[i].v; tl++; if(tl>n+1) tl-=n+1;
}
}
}
inq[u] = false;
}
return dis[t]!=-INF2;
}
void calcflow()
{
int flow = 1e5;
for(int u=t; u!=s; u=e[lst[u]].u)
{
flow = min(flow,e[lst[u]].w);
}
for(int u=t; u!=s; u=e[lst[u]].u)
{
e[lst[u]].w -= flow; e[lst[u]^1].w += flow;
}
mf += flow; mc += dis[t]*(lllong)flow;
}
void mfmc()
{
mf = mc = 0; while(spfa()) {calcflow();}
}
void addedge(int u,int v,int wl,int wr,llong c)
{
m++; ae[m].u = u,ae[m].v = v,ae[m].wl = wl,ae[m].wr = wr,ae[m].c = c;
}
llong flow(int _n,int _s,int _t,int _mf)
{
n = _n,s = _s,t = _t; en = 1; lllong ret = 0ll;
for(int i=1; i<=m; i++)
{
if(ae[i].wl) {addedge0(ae[i].u,ae[i].v,ae[i].wl,INF); ret += (ae[i].c-INF)*(lllong)ae[i].wl;}
addedge0(ae[i].u,ae[i].v,ae[i].wr-ae[i].wl,ae[i].c);
}
mfmc();
if(mf!=_mf||mc+ret<(lllong)0) {return -1ll;}
return mc+ret;
}
}
const int N = 100;
struct Element
{
int x,y; llong w;
} a[N+3];
struct Condition
{
int typ,x,y;
} b[N*4+3];
int alx[N+3],aly[N+3],arx[N+3],ary[N+3];
int n,m,mx; llong ans;
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].w); mx = max(mx,max(a[i].x,a[i].y));
}
scanf("%d",&m);
for(int i=1; i<=m; i++)
{
char str[5]; scanf("%s%d%d",str,&b[i].x,&b[i].y); mx = max(mx,b[i].x);
b[i].typ = (str[0]=='L'?0:(str[0]=='R'?1:(str[0]=='D'?2:3)));
}
mx++;
for(int k=1; k<=n; k++)
{
for(int i=0; i<=mx; i++) alx[i] = 0,arx[i] = k,aly[i] = 0,ary[i] = k;
for(int i=1; i<=m; i++)
{
if(b[i].typ==0)
{
alx[b[i].x+1] = max(alx[b[i].x+1],k-b[i].y);
}
else if(b[i].typ==1)
{
arx[b[i].x] = min(arx[b[i].x],b[i].y);
}
else if(b[i].typ==2)
{
ary[b[i].x] = min(ary[b[i].x],b[i].y);
}
else if(b[i].typ==3)
{
aly[b[i].x-1] = max(aly[b[i].x-1],k-b[i].y);
}
}
bool ok = true;
for(int i=0; i<=mx; i++) {if(alx[i]>arx[i]||aly[i]>ary[i]) {ok = false; break;}}
if(!ok) continue;
NetFlow::init();
for(int i=0; i<=mx; i++)
{
NetFlow::addedge(i==0?1:i+2,i+3,alx[i],arx[i],0ll);
}
for(int i=0; i<=mx; i++)
{
NetFlow::addedge(i+mx+4,i==mx?2:i+mx+5,aly[i],ary[i],0ll);
}
for(int i=1; i<=n; i++)
{
NetFlow::addedge(a[i].x+3,a[i].y+mx+4,0,1,a[i].w);
}
llong cur = NetFlow::flow(mx+mx+4,1,2,k);
ans = max(ans,cur);
}
printf("%lld
",ans);
return 0;
}