NC207426. 养花
描述
输入描述
输入数据第一行是t,表示数据的组数,接下来每组数据输入n,m,k,
接下来一行输入n个数,分别是每棵植物的高度h[i](1 <= h[i] < k),
接下来m行开头的两个数字为op和c表示药水是哪一种和该种药水有几瓶,输入如下
若 op=1,则接下来两个整数 a0,b0,意义如上文所述。
若 op=2,则接下来三个整数 a1,a2,b1,意义如上文所述。
若 op=3,则接下来三个整数 a1,b1,b2,意义如上文所述。
若 op=4,则接下来四个整数 a1,a2,b1,b2,意义如上文所述。
数据保证,所有 1 <= a0,b0,a1,b1,a2,b2 <= k
(t <= 10,n <= 1e4,m <= 300,k <= 100,c <=1e6)
输出描述
输出一个整数,表示最多有多少颗植物能生涨到k。
示例1
输入:
1 5 4 5 1 1 1 1 1 1 3 1 3 1 3 3 2 1 3 2 5 4 1 1 1 4 5
输出:
4
C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 624K, 提交时间: 2020-05-31 15:22:13
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define sz(x) (int)x.size() #define all(x) begin(x), end(x) #define fi first #define se second #define debug(x) cerr << #x << " " << x << '\n' using namespace std; using ll = long long; using pii = pair<int,int>; using pli = pair<ll,int>; const int INF = 0x3f3f3f3f; const ll LINF = 1e18 + 5; constexpr int mod = 1e9 + 7; int n, m, k, c, h, sum[105], w[105][105]; const int N = 105, M = 1e5 + 5; int cnt, head[N]; struct node { int next, to, w; }e[M<<1]; inline void add(int u,int v,int w) { e[++cnt].next = head[u]; e[cnt].to = v; e[cnt].w = w; head[u] = cnt; } struct Dinic { int n, m, s, t; int dep[N], cur[N]; void init(int n,int s,int t) { this->s = s, this->t = t, this->n = n; cnt = 1, m = 0; memset(head,0,(n+1)*sizeof(int)); } void addedge(int u,int v,int cap) { add(u,v,cap); add(v,u,0); m += 2; } bool bfs() { memset(dep,0,(n+1)*sizeof(int)); memcpy(cur,head,(n+1)*sizeof(int)); queue <int> q; q.push(s); dep[s] = 1; while(!q.empty()) { int u = q.front(); q.pop(); for(int i=head[u];i;i=e[i].next) { int v = e[i].to; if(!dep[v]&&e[i].w>0) { dep[v] = dep[u] + 1; q.push(v); } } } return dep[t]; } int dfs(int u,int flow) { if(u==t||!flow) return flow; int used = flow; for(int i=cur[u];i;i=e[i].next) { cur[u] = i; int v = e[i].to; if(dep[v]==dep[u]+1) { int low = dfs(v,min(flow,e[i].w)); e[i].w -= low; e[i^1].w += low; flow -= low; if(!flow) break; } } return used - flow; } int go() { int maxflow = 0; while(bfs()) maxflow += dfs(s,INF); return maxflow; } }MF; void solve() { scanf("%d%d%d", &n, &m, &k); memset(sum, 0, sizeof(sum)); memset(w, 0, sizeof(w)); MF.init(k+2, 0, k+1); for(int i=1; i<=n; i++) { scanf("%d", &h); sum[h]++; } for(int i=1; i<=m; i++) { int op; scanf("%d%d", &op, &c); if(op==1) { int a0, b0; scanf("%d%d", &a0, &b0); w[a0][b0] += c; } else if(op==2) { int a1, a2, b1; scanf("%d%d%d", &a1, &a2, &b1); for(int i=a1; i<=a2; i++) w[i][b1] += c; } else if(op==3) { int a1, b1, b2; scanf("%d%d%d", &a1, &b1, &b2); for(int i=b1; i<=b2; i++) w[a1][i] += c; } else { int a1, a2, b1, b2; scanf("%d%d%d%d", &a1, &a2, &b1, &b2); for(int i=a1; i<=a2; i++) for(int j=b1; j<=b2; j++) w[i][j] += c; } } for(int i=1; i<=k; i++) for(int j=1; j<=k; j++) if(i!=j) MF.addedge(i, j, w[i][j]); for(int i=1; i<=k; i++) MF.addedge(MF.s, i, sum[i]); MF.addedge(k, MF.t, INF); printf("%d\n", MF.go()); } int main() { int T; scanf("%d", &T); while(T--) solve(); return 0; }
C++11(clang++ 3.9) 解法, 执行用时: 14ms, 内存消耗: 620K, 提交时间: 2020-06-01 01:38:33
#include<bits/stdc++.h> using namespace std; const int N=2011,inf=1e9+11; struct Side{ int v,ne,w; }S[N*200]; int num,cnt[N]; int n,sn,sb,se,head[N],dep[N],cur[N]; void initS(){ sn=0; for(int i=0;i<N;i++) head[i]=-1; } void addS(int u,int v,int w){ S[sn].w=w;S[sn].v=v; S[sn].ne=head[u]; head[u]=sn++; } void addE(int u,int v,int w){ addS(u,v,w);addS(v,u,0); } bool bfs(){ queue<int> q; for(int i=sb;i<=se;i++) dep[i]=0; dep[sb]=1; q.push(sb); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];~i;i=S[i].ne){ int v=S[i].v; if(!dep[v]&&S[i].w>0){ dep[v]=dep[u]+1; q.push(v); } } } return dep[se]!=0; } int dfs(int u,int minf){ if(u==se||!minf) return minf; for(int &i=cur[u];~i;i=S[i].ne){ int v=S[i].v; if(S[i].w>0&&dep[v]==dep[u]+1){ int flow=dfs(v,min(minf,S[i].w)); if(flow>0){ S[i].w-=flow; S[i^1].w+=flow; return flow; } } } return 0; } int dinic(){ int ans=0,flow=0; while(bfs()){ for(int i=sb;i<=se;i++) cur[i]=head[i]; while(flow=dfs(sb,inf)) ans+=flow; } return ans; } int main(){ int t; scanf("%d",&t); while(t--){ int n,m,k,x; scanf("%d%d%d",&n,&m,&k); for(int i=0;i<=k;i++) cnt[i]=0; for(int i=0;i<n;i++){ scanf("%d",&x); cnt[x]++; } initS(); num=k; int op,c,a1,b1,a2,b2; for(int i=1;i<=m;i++){ scanf("%d%d",&op,&c); if(op==1){ scanf("%d%d",&a1,&b1); addE(a1,b1,c); }else if(op==2){ scanf("%d%d%d",&a1,&a2,&b1); ++num; for(int j=a1;j<=a2;j++) addE(j,num,c); addE(num,b1,c); }else if(op==3){ scanf("%d%d%d",&a1,&b1,&b2); ++num; addE(a1,num,c);; for(int j=b1;j<=b2;j++) addE(num,j,c); }else{ scanf("%d%d%d%d",&a1,&a2,&b1,&b2); ++num; for(int j=a1;j<=a2;j++) addE(j,num,c); addE(num,num+1,c); ++num; for(int j=b1;j<=b2;j++) addE(num,j,c); } } sb=0;se=++num; for(int i=1;i<=k;i++) addE(sb,i,cnt[i]); addE(k,se,inf); printf("%d\n",dinic()); } return 0; }