HDU 6611 K Subsequence (djistra优化的费用流)

mac2022-06-30  142

大致题意

给一个长度为 n 的序列 ai,现要求 k 条不上升子序列,使得他们的权值和最大。求最大值。 n的范围好像是1000

思路

容易想到拆点最大费用流,首先把每个点 i 拆成 2 个,i 向 i’ 连一条容量为 1 费用为 ai 的边,限制每个数字只能用一次,然后寻找 ai >= aj ,然后 i’ 向 j 连一条 容量为1 费用为 0 的边。最后起点终点连起来,然后再建一个超前起点se 连一条 容量为 k 费用为 0 的边,终点也可以一样搞一下。 然后我原来的spfa优化的费用流板子一直TLE,可见spfa真的死了,可能这个建图就是网格图?? 然后上网上找了一个巨巨的djistra优化的板子,好像比较高级,有用势解决负权的功能,然后这里要求最大费用,所以要建负边,要多用用才知道这玩意。 有空研究研究。

代码

/******* dijkstra优化费用流模板 *******/ //不能有负环 #include<bits/stdc++.h> using namespace std; #define maxn 4005 #define maxm 1006 #define ll long long int #define INF 0x3f3f3f3f #define inc(i,l,r) for(int i=l;i<=r;i++) #define dec(i,r,l) for(int i=r;i>=l;i--) #define mem(a) memset(a,0,sizeof(a)) #define sqr(x) (x*x) #define inf (ll)2e18+1 #define PI acos(-1) #define mod 10007 #define auto(i,x) for(int i=head[x];i;i=ed[i].nxt) #define ls x<<1 #define rs x<<1|1 ll read(){ ll x=0,f=1ll;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return f*x; } int n,m,b[maxn],T; int s,t,se,te; //不能有负环 #include<functional> //C++编译需要头文件 typedef pair<int, int> pii;//first保存最短距离,second保存顶点的编号 struct edge { int to, cap, cost, rev; //终点,容量(指残量网络中的),费用,反向边编号 edge() {} edge(int to, int _cap, int _cost, int _rev):to(to), cap(_cap), cost(_cost), rev(_rev) {} }; int V; //顶点数 int h[maxn]; //顶点的势 int dis[maxn]; //最短距离 int prevv[maxn];//最短路中的父结点 int pree[maxn]; //最短路中的父边 vector<edge> G[maxn]; //图的邻接表 void init(int n) { V = n; for(int i = 0; i <= V; ++i) G[i].clear(); } void addEdge(int from, int to, int cap, int cost){ G[from].push_back(edge(to, cap, cost, G[to].size())); G[to].push_back(edge(from, 0, -cost, G[from].size() - 1)); } int MCMF(int s, int t, int f, int &flow){ //f为最多能流多少 int res = 0; for(int i = 0; i < 1 + V; i++) h[i] = 0; while(f){ priority_queue<pii, vector<pii>, greater<pii> > q; for(int i = 0; i < 1 + V; i++) dis[i] = INF; dis[s] = 0; q.push(pii(0, s)); while(!q.empty()) { pii now = q.top(); q.pop(); int v = now.second; if(dis[v] < now.first) continue; for(int i = 0; i < G[v].size(); ++i) { edge &e = G[v][i]; if(e.cap > 0 && dis[e.to] > dis[v] + e.cost + h[v] - h[e.to]){ dis[e.to] = dis[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v; pree[e.to] = i; q.push(pii(dis[e.to], e.to)); } } } if(dis[t] == INF) break; for(int i = 0; i <= V; ++i) h[i] += dis[i]; int d = f; for(int v = t; v != s; v = prevv[v]) d = min(d, G[prevv[v]][pree[v]].cap); f -= d; flow += d; res += d * h[t]; for(int v = t; v != s; v = prevv[v]) { edge &e = G[prevv[v]][pree[v]]; e.cap -= d; G[v][e.rev].cap += d; } } return res; } int main() { T=read(); while(T--){ n=read();m=read(); s=2*n+1;t=s+1;se=s+2;te=s+3; init(te); inc(i,1,n)b[i]=read(); inc(i,1,n)addEdge(i,i+n,1,-b[i]),addEdge(s,i,1,0),addEdge(i+n,t,1,0); inc(i,1,n)inc(j,i+1,n)if(b[i]<=b[j])addEdge(i+n,j,1,0); addEdge(se,s,m,0);addEdge(t,te,m,0); int ans; printf("%d\n",-MCMF(se,te,INF,ans)); } return 0; }
最新回复(0)