题目链接
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(n\cdot 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 __int128const 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\n",ans);return 0;
}
