牛客练习赛51 D 羊吃草
- 2019 年 10 月 4 日
- 筆記
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_41603898/article/details/100593523
建图没什么好说的，跑最大流原来的权值会被破坏，需要记录重新赋值。
#include <bits/stdc++.h> using namespace std; #define ll long long #define INF 0x7ffffff const int M = 1000005; const int inf = 0x7fffffff; struct E { int nxt,u,v,w; int yuanw; }; E edg[M]; int d[M],head[M],cnt; int s,t,n,m; void init() { cnt = 0; memset(head,-1,sizeof head); } void add(int u,int v,int w) { edg[cnt].v = v; edg[cnt].u = u; edg[cnt].w = w; edg[cnt].yuanw = w; edg[cnt].nxt = head[u]; head[u] = cnt++; edg[cnt].v = u; edg[cnt].u = v; edg[cnt].w = 0; edg[cnt].yuanw = 0; edg[cnt].nxt = head[v]; head[v] = cnt++; } bool bfs(int s,int t,int l,int r) { queue<int> q; memset(d,0,sizeof d); q.push(s); d[s] = 1; while(!q.empty()) { int top = q.front(); q.pop(); for(int i = head[top]; i + 1; i = edg[i].nxt) { int v = edg[i].v,w = edg[i].w; if(v>400&&v!=s&&v!=t) { if(v<l||v>r)continue; } if(!d[v] && w) { d[v] = d[top] + 1; q.push(v); } } } return d[t] > 0; } int dfs(int s,int t,int inflow,int l,int r) { if(s == t || !inflow) return inflow; int flow = 0; for(int i = head[s]; i + 1; i = edg[i].nxt) { int v = edg[i].v,w = edg[i].w; if(v>400&&v!=s&&v!=t) { if(v<l||v>r)continue; } if(w && d[v] == d[s] + 1) { int x = dfs(v,t,min(inflow,w),l,r); edg[i].w -= x; edg[i ^ 1].w += x; inflow -= x; flow += x; if(!inflow) break; } } if(!flow) d[s] = -2; return flow; } long long dinic(int s,int t,int l,int r) { long long ans = 0; while(bfs(s,t,l,r)) ans += dfs(s,t,inf,l,r); return ans; } struct N { int l,r; } no[405]; int main() { int a,b,c; scanf("%d %d",&n,&m); int s = 1001, t = 1002; init(); ll ans = 0; for(int i=1; i<=n; i++) { scanf("%d",&no[i].l); } for(int i=1; i<=n; i++) { scanf("%d",&no[i].r); } for(int i=1; i<=n; i++) { add(s,i,1); for(int l = no[i].l;l<=no[i].r; l++) { add(i,l+400,1); } } for(int i=1;i<=400;i++){ add(i+400,t,1); } int l,r; while(m--) { scanf("%d %d",&l,&r); printf("%lldn",dinic(s,t,l+400,r+400)); for(int i=0;i<cnt;++i){ edg[i].w = edg[i].yuanw; } } return 0; }
