养花

题解：

这题的掌握网络流中的最大流相关知识。

因为k<=100,那么我们可以把1~k的数看成点，而下面的药水便可以看做点之间有流量的边，那么题目的要求便成了1~k的这些点，能有多少流量通过给出的边流到k点。

因为1~k的数都可以看做起点，所以我们创建个源点与它们各连一条边，流量便是由多少种高度为这个数的植物。

而创建个汇点与k点连一条边，流量为无穷大即可，最后就是看能有多少流量流到汇点。

对于药水1,a0可以变成b0，所以直接便是建一条a0到b0的边，流量为该药水有几瓶

对于药水2，a1~a2可以变成b1,这时我们不能直接对a1~a2每个点都建一条到b1的边，因为这样相当于药水2有（a2-a1+1）*c瓶了，所以我们需要加点，创建个中间节点x，让a1~a2的点都建一条边，流量>=c即可，然后该x再建一条到b1的边，流量为c,由此便控制了药水2只有c瓶。

药水3和药水4也是同理，建完边，跑一遍最大流的模板即可。

AC_Code:

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int maxn=2011;
  4 const int inf=0x3f3f3f3f;
  5 struct Side{
  6     int to,nxt,w;
  7 }S[maxn*200];
  8 int num,cnt[maxn];
  9 int n,tot,st,ed,head[maxn],dep[maxn],cur[maxn];
 10 void initS(){
 11     tot=0;
 12     for(int i=0;i<maxn;i++) head[i]=-1;
 13 }
 14 void addS(int u,int v,int w){
 15     S[tot].w=w;S[tot].to=v;
 16     S[tot].nxt=head[u];
 17     head[u]=tot++;
 18 }
 19 void addE(int u,int v,int w){
 20     addS(u,v,w);addS(v,u,0);
 21 }
 22 bool bfs(){
 23     queue<int> q;
 24     for(int i=st;i<=ed;i++) dep[i]=-1;
 25     dep[st]=0;
 26     q.push(st);
 27     while(!q.empty()){
 28         int u=q.front();
 29         q.pop();
 30         for(int i=head[u];~i;i=S[i].nxt){
 31             int v=S[i].to;
 32             if(dep[v]==-1&&S[i].w>0){
 33                 dep[v]=dep[u]+1;
 34                 q.push(v);
 35                 if( v==ed ) return true;
 36             }
 37         }
 38     }
 39     return dep[ed]!=-1;
 40 }
 41 int dfs(int u,int minf){
 42     if(u==ed||!minf) return minf;
 43     int curr=0;
 44     for(int &i=cur[u];~i;i=S[i].nxt){
 45         int v=S[i].to;
 46         if(S[i].w>0&&dep[v]==dep[u]+1){
 47             int flow=dfs(v,min(minf,S[i].w));
 48             if(flow>0){
 49                 S[i].w-=flow;
 50                 S[i^1].w+=flow;
 51                 curr+=flow;
 52                 minf-=flow;
 53 //                return flow;
 54                 if( minf==0 ) break;
 55             }
 56         }
 57     }
 58     if( curr==0 ) dep[u]=inf;
 59     return curr;
 60 }
 61 int dinic(){
 62     int flow=0;
 63     while(bfs()){
 64         for(int i=st;i<=ed;i++) cur[i]=head[i];
 65         flow+=dfs(st,inf);
 66     }
 67     return flow;
 68 }
 69 int main(){
 70     int t;
 71     scanf("%d",&t);
 72     while(t--){
 73         int n,m,k,x;
 74         scanf("%d%d%d",&n,&m,&k);
 75         for(int i=0;i<=k;i++) cnt[i]=0;
 76         for(int i=0;i<n;i++){
 77             scanf("%d",&x);
 78             cnt[x]++;
 79         }
 80         initS();
 81         num=k;
 82         int op,c,a1,b1,a2,b2;
 83         for(int i=1;i<=m;i++){
 84             scanf("%d%d",&op,&c);
 85             if(op==1){
 86                 scanf("%d%d",&a1,&b1);
 87                 addE(a1,b1,c);
 88             }else if(op==2){
 89                 scanf("%d%d%d",&a1,&a2,&b1);
 90                 ++num;
 91                 for(int j=a1;j<=a2;j++) addE(j,num,c);
 92                 addE(num,b1,c);
 93             }else if(op==3){
 94                 scanf("%d%d%d",&a1,&b1,&b2);
 95                 ++num;
 96                 addE(a1,num,c);;
 97                 for(int j=b1;j<=b2;j++) addE(num,j,c);
 98             }else{
 99                 scanf("%d%d%d%d",&a1,&a2,&b1,&b2);
100                 ++num;
101                 for(int j=a1;j<=a2;j++) addE(j,num,c);
102                 addE(num,num+1,c);
103                 ++num;
104                 for(int j=b1;j<=b2;j++) addE(num,j,c);
105             }
106         }
107         st=0;ed=++num;
108         for(int i=1;i<=k;i++) addE(st,i,cnt[i]);
109         addE(k,ed,inf);
110         printf("%d
",dinic());
111     }
112     return 0;
113 }