锐客网

  1. 首页 > 睿知 > it技术 > >

HDU - 5406 CRB and Apple (费用流)

IT知识apple费用费用流

盛年不重来，一日难再晨，及时当勉励，岁月不待人。这篇文章主要讲述HDU - 5406 CRB and Apple (费用流)相关的知识，希望能为你提供帮助。
【HDU - 5406 CRB and Apple (费用流)】题意：对于给定的物品，求两个在高度上单调不递增，权值上单调不递减的序列，使二者长度之和最大。
分析：可以用费用流求解，因为要求长度和最大，视作从源点出发的流量为2的费用流，建负权边，每个物品只能取一次，且花费为-1。将每个物品拆成入点和出点，中间建容量为1，费用为-1的弧。建源点s和超级源点S，S到s建容量为2，费用为0的弧，表示只有两个序列。源点s向每个入点建容量为1，费用为0的弧，表示每个点都可作为序列的首项。出点向汇点建容量为1，费用为0的弧，表示每个点都可作为序列的末项。
对给定物品按高度和权值排序后，从权值较小的物品向权值较大的物品建边，容量为1，花费为0。
跑出费用流后对花费取反就是答案。spfa要用栈优化，队列会T。

#include< iostream> #include< cstring> #include< stdio.h> #include< algorithm> #include< string> #include< cmath> #include< set> #include< map> #include< vector> #include< stack> #include< queue> using namespace std; const int MAXN = 2005; const int MAXM = 2000005; const int INF = 0x3f3f3f3f; struct Edge{ int to, next, cap, flow, cost; } edge[MAXM]; int head[MAXN], tot; int pre[MAXN], dis[MAXN]; bool vis[MAXN]; int N; void init(int n) { N = n; tot = 0; memset(head, -1, sizeof(head)); }void AddEdge(int u, int v, int cap, int cost) { edge[tot] = (Edge){v,head[u],cap,0,cost}; head[u] = tot++; edge[tot] = (Edge){u,head[v],0,0,-cost}; head[v] = tot++; }bool spfa(int s, int t){ stack< int> q; for (int i = 0; i < N; i++){ dis[i] = INF; vis[i] = false; pre[i] = -1; } dis[s] = 0; vis[s] = true; q.push(s); while (!q.empty()){ int u = q.top(); q.pop(); vis[u] = false; for (int i = head[u]; i != -1; i = edge[i].next){ int v = edge[i].to; if (edge[i].cap > edge[i].flow & & dis[v] > dis[u] + edge[i].cost){ dis[v] = dis[u] + edge[i].cost; pre[v] = i; if (!vis[v]){ vis[v] = true; q.push(v); } } } } if (pre[t] == -1) return false; elsereturn true; }int minCostMaxflow(int s, int t, int & cost){ int flow = 0; cost = 0; while (spfa(s, t)){ int Min = INF; for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]){ if (Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow; } for (int i = pre[t]; i != -1; i = pre[edge[i ^ 1].to]){ edge[i].flow += Min; edge[i ^ 1].flow -= Min; cost += edge[i].cost * Min; } flow += Min; } return flow; }struct Node{ int h,w; bool operator< (const Node & rhs) const{ if(h==rhs.h) return w< rhs.w; return h> rhs.h; } }vz[MAXN]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int T; scanf("%d",& T); while(T--){ int N; scanf("%d",& N); int u,v; for(int i=1; i< =N; ++i){ scanf("%d %d",& vz[i].h,& vz[i].w); } sort(vz+1,vz+N+1); init(2*N+4); int s = 2*N+1, t = 2*N+2; int S = 0; for(int i=1; i< =N; ++i){ AddEdge(i+N,t,1,0); AddEdge(s,i,1,0); AddEdge(i,i+N,1,-1); int x = INF; for(int j=i+1; j< =N; ++j){ if(vz[i].w< =vz[j].w){ AddEdge(i+N,j,1,0); } } } AddEdge(S,s,2,0); int cost; minCostMaxflow(S,t,cost); printf("%d ",-cost); } return 0; }





    推荐阅读


    上一篇：SVg中的链接用法示例

    下一篇：深入理解Android之View的绘制流程