題目鏈接

https://atcoder.jp/contests/agc031/tasks/agc031_e

題解

做法一（我的做法）

這是我yy出來的一個(gè)上下界費(fèi)用流做法，自己沒找到什么反例，能過。（一開始一直WA以為做法假了結(jié)果發(fā)現(xiàn)寫錯(cuò)了一個(gè)sb地方摔）如果有什么問題敬請指出，謝謝。
考慮一維怎么做，首先可以枚舉一共選多少個(gè)，那么對每個(gè)位置的限制就相當(dāng)于“前\(i\)個(gè)里選的個(gè)數(shù)在\([L_i,R_i]\)之間”。
我們可以給每個(gè)位置建一個(gè)點(diǎn)，源點(diǎn)往\(1\)號(hào)位置的點(diǎn)連\(([0,+\infty],0)\), \(i\)往\((i+1)\)連\(([L_i,R_i],0)\), \(i\)往匯點(diǎn)連\(([0,1],w_i)\), 跑最大費(fèi)用最大流即可。
然后拓展到二維：我們給每一行每一列分別建一個(gè)點(diǎn)，記作\(R_i,C_j\). 對每個(gè)物品\(u\), 從\(R_{x_u}\)往\(C_{y_u}\)連\(([0,1],w_u)\). 設(shè)限制形如“從第\(i\)行到最后一行選的個(gè)數(shù)在\([LX_i,RX_i]\)之間”、“前\(j\)列選的個(gè)數(shù)在\([LY_j,RY_j]\)之間”，則從\(R_{i-1}\)向\(R_i\)連\(([LX_i,RX_i],0)\) (特別地，\(i=0\)時(shí)起點(diǎn)為源點(diǎn))，從\(C_j\)向\(C_{j+1}\)連\(([LY_j,RY_j],0)\) (特別地，\(j=MX\)時(shí)終點(diǎn)為匯點(diǎn),\(MX\)為最大坐標(biāo))，跑最大費(fèi)用流就可以了。
這里上下界網(wǎng)絡(luò)流因?yàn)樽畲罅饕阎?#xff0c;我采用的是把每條邊的下界費(fèi)用設(shè)為無窮大的寫法，需要使用__int128. 有其他的寫法但是博主太菜了不會(huì)……
時(shí)間復(fù)雜度\(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; }

總結(jié)

以上是生活随笔為你收集整理的AtCoder AGC031E Snuke the Phantom Thief (费用流)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。