网络流

h<=50?

直接都选择最大的，ans=n*h*h

最小割

 

考虑舍弃或者罚款

有一个>x就要罚款？

经典取值限制的模型：切糕割！

每个位置的x+1到额外点tot连接inf边

tot向t连接c边

大概这样：

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=55;const int P=N*N;const int inf=0x3f3f3f3f;int n,m,h;int s,t;struct node{ int nxt,to; int w;}e[2*(P+P+N*N)];int hd[P],cnt=1;void add(int x,int y,int z){ e[++cnt].nxt=hd[x]; e[cnt].to=y;e[cnt].w=z; hd[x]=cnt; e[++cnt].nxt=hd[y]; e[cnt].to=x;e[cnt].w=0; hd[y]=cnt;}int d[P];int q[P],l,r;int ans;int dfs(int x,int flow){ int res=flow; if(x==t) return flow; for(reg i=hd[x];i&&res;i=e[i].nxt){ int y=e[i].to; if(d[y]==d[x]+1&&e[i].w){ int k=dfs(y,min(res,e[i].w)); if(!k) d[y]=0; res-=k; e[i].w-=k; e[i^1].w+=k; } } return flow-res;}bool bfs(){ memset(d,0,sizeof d); l=1,r=0; q[++r]=s; d[s]=1; while(l<=r){ int x=q[l++]; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(e[i].w&&!d[y]){ d[y]=d[x]+1; q[++r]=y; if(y==t) return true; } } } return false;}int num(int x,int y){ return (x-1)*(h+1)+y+1;}int main(){ rd(n);rd(h);rd(m); ans=n*h*h; s=0;t=num(n,h)+1; int tot=t; for(reg i=1;i<=n;++i){ add(s,num(i,0),inf); for(reg j=0;j