原题的话,由于保证了wi<wi+1,是一个比较simple的费用流啦。
如果不保证wi递增的话，也可以有一个比较暴力的复杂度和流量相关的做法。
#include#include #include #include #include #include #include #include #include #include #define N 220000#define M 220000#define L 200000#define eps 1e-7#define inf 1e9+7#define ll long longusing namespace std;inline int read(){ char ch=0; int x=0,flag=1; while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*flag;}struct edge{ int to,nxt,flow,w;}e[M];int num,head[N];inline void add(int x,int y,int w,int z){ e[++num]=(edge){y,head[x],w,+z};head[x]=num; e[++num]=(edge){x,head[y],0,-z};head[y]=num;}queue q;bool in_queue[N];int s,t,T[N],W[N],dis[N],pre[N],last[N],flow[N];bool spfa(){ for(int i=0;i<=t;i++)dis[i]=flow[i]=inf; dis[s]=0;q.push(s);in_queue[s]=true; while(!q.empty()) { int x=q.front(); q.pop();in_queue[x]=false; for(int i=head[x];i!=-1;i=e[i].nxt) { int to=e[i].to; if(dis[to]>dis[x]+e[i].w&&e[i].flow) { dis[to]=dis[x]+e[i].w; flow[to]=min(flow[x],e[i].flow); pre[to]=x;last[to]=i; if(!in_queue[to])q.push(to),in_queue[to]=true; } } } return dis[t]