https://odzkskevi.qnssl.com/7dfb262544887eff6fb35bfb444759d6?v=1502084197

 

做法是类似于最大割之类的东西，把每个碎片按照按钮拆点，从s到每个碎片第一个点连inf，每个碎片第i个按钮向第i+1个按钮连100-i能量。

然后最大流最小割，最大流=割掉的边和=100*n-能量和的最大值。

 

#include
      
       #include
       
        #include
        
         #include
         
          #define rep(i,l,r) for(int i=l;i<=r;i++)#define dow(i,l,r) for(int i=r;i>=l;i--)#define rep0(i,r) for(int i=0;i
          
           =0;i=e[i].next)#define maxn 20020#define maxm 200100#define LL long longusing namespace std;typedef struct {    int next,f,t;}E;E e[maxm];int gap[maxn],d[maxn],fi[maxn],cur[maxn],s,t,total=0;const int inf=100000000;int n,m,q;void add(int j,int k,int l){    e[total].f=l;    e[total].t=k;    e[total].next=fi[j];    fi[j]=total;    total++;}void addedge(int j,int k,int l){    add(j,k,l);    add(k,j,0);}int sap(int x,int flow){    if (x==t) return flow;    int now=0;    repedge(i,x) {        int too=e[i].t;        if (d[too]+1==d[x] && e[i].f) {            int more=sap(too,min(e[i].f,flow-now));            e[i].f-=more;            e[i^1].f+=more;            cur[x]=i;            if (flow==(now+=more)) return flow;        }    }    if (!(--gap[d[x]])) d[s]=t;    gap[++d[x]]++;    cur[x]=fi[x];    return now;}int maxflow(){    memset(d,0,sizeof(d));    memset(gap,0,sizeof(gap));    rep(i,1,t) cur[i]=fi[i];    gap[0]=t;    int ans=0;    while (d[s]
          
         
        
       
      

 

• 我1