列表

详情


NC207426. 养花

描述

小明是一个魔法师,他有n棵植物,所有植物排成一排,植物的初始高度为数组h,小明有一些强迫症,他想
让植物的高度都恰好达到k,小明有m瓶药水,但药水分为4种:
1.选择一棵高度为a0的植物变为b0高度的植物
2.选择一棵高度在[a1,a2]区间内的植物变为b1高度的植物
3.选择一棵高度为a1的植物变为[b1, b2]区间内某一高度的植物
4.选择一棵高度在[a1,a2]区间内的植物变为[b1,b2]区间内某一高度的植物
由于每瓶药水有C瓶库存,小明想知道他最多让多少棵植物高度达到k

输入描述

输入数据第一行是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;
}

上一题