HDU 5406【费用流 或 dp+树状数组】

2024-08-24 11:38
文章标签 数组 dp 树状 费用 hdu 5406

本文主要是介绍HDU 5406【费用流 或 dp+树状数组】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

拆点,容量为1表示每个点只能用一次,费用为-1表示经过了几个点
建立超级源向源点连接容量为2的边,表示两个上升序列。

spfa用了栈就可以过了。

//      whn6325689
//      Mr.Phoebe
//      http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62
#define speed std::ios::sync_with_stdio(false);typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define CPY(x,y) memcpy(x,y,sizeof(x))
#define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
#define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
#define debug(a) cout << #a" = " << (a) << endl;
#define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))#define MID(x,y) (x+((y-x)>>1))
#define ls (idx<<1)
#define rs (idx<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,rtemplate<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int N=2005,M=2000005;
struct Graph
{struct node{int v,next,w,flow;node(){};node(int a,int b,int c,int d){next=a;v=b;w=c;flow=d;}}E[2*M];int head[N],pre[N],dis[N];int beg,end,flow,cost;bool h[N];int path[N];int NE,NV;void resize(int n){this->NV=n;}void init(int n){NE=0;NV=n;memset(head,-1,sizeof(int)*(n+10));}void insert(int u,int v,int flow,int w){E[NE]=node(head[u],v,w,flow);head[u]=NE++;E[NE]=node(head[v],u,-w,0);head[v]=NE++;}bool update(int u,int v,int w){if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;return true;}return false;}int st[N];bool spfa(){CLR(pre,-1);CLR(h,0);for(int i=0;i<=NV;i++)dis[i]=INF;dis[beg]=0;int top=0;st[top++]=beg;while(top){top--;int u=st[top];h[u]=0;for(int i=head[u];i!=-1;i=E[i].next){int v=E[i].v;if(E[i].flow>0&&update(u,v,E[i].w)){pre[v]=u;path[v]=i;if(!h[v]){h[v]=1;st[top++]=v;}}}}if(pre[end]==-1)return false;return true;}int mincost_maxflow(int s,int t){this->beg=s;this->end=t;flow=0,cost=0;while(spfa()){int Min=INT_MAX;for(int i=end;i!=beg;i=pre[i])if(Min>E[path[i]].flow)Min=E[path[i]].flow;for(int i=end;i!=beg;i=pre[i]){E[path[i]].flow-=Min;E[path[i]^1].flow+=Min;}flow+=Min;cost+=dis[end];}return cost;}
}g;struct apple
{int h,v;
}a[N];bool cmp(apple a,apple b)
{if(a.h==b.h) return a.v<b.v;return a.h>b.h;
}
int n,i,j,s,t,ss;
const int MAXN=3000;int main()
{int T;scanf("%d",&T);while (T--){scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d%d",&a[i].h,&a[i].v);sort(a+1,a+1+n,cmp);s=0;t=2*n+2;ss=2*n+1;g.init(2*n+3);g.insert(s,ss,2,0);for(i=1;i<=n;i++){g.insert(ss,i,1,0);g.insert(i,n+i,1,-1);g.insert(n+i,t,1,0);}for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)if(a[i].v<=a[j].v)g.insert(n+i,j,1,0);int ans=g.mincost_maxflow(s,t);printf("%d\n",-ans);}return 0;
}

建图图上进行dp,dp[i][j]表示表示两个人分别在 第i个点和第j个点时候能吃的最多苹果树,可以限制下 i<=j减少有效状态,还有就是一些无用的边不需要构造出来 ,比如说

a->b b->c 那么 就不需要连a->c的边,这里边表示的是 吃完a可以吃b。然后就图上跑一遍dp就行了。注意事项见代码。

#include <queue>
#include <limits>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
#define INF 1000000050
#define MAXN 1111
vector<int> e[MAXN];
int in[MAXN];
int q[MAXN];
int dis[MAXN];
int d[MAXN][MAXN];
int id[MAXN];
struct g {int h, d;
} s[MAXN];
bool cmp(g a, g b) {if (a.h == b.h)return a.d < b.d;return a.h > b.h;
}int main() {int tt;scanf("%d", &tt);while (tt--) {int n;scanf("%d", &n);for (int i = 1; i <= n; ++i)scanf("%d%d", &s[i].h, &s[i].d);sort(s + 1, s + 1 + n, cmp);for (int i = 0; i <= n + 1; ++i) {dis[i] = in[i] = 0;e[i].clear();}//进行拓扑排序,根据拓扑序进行dpfor (int i = 1; i <= n; ++i) {e[0].push_back(i);in[i]++;for (int j = i + 1; j <= n; ++j) {if (s[i].d <= s[j].d) {e[i].push_back(j);in[j]++;}}e[i].push_back(n + 1);in[n + 1]++;}int tail = 0;q[tail++] = 0;dis[0] = 0;id[0] = 0;for (int i = 0; i < tail; ++i) {int u = q[i];id[u] = i;for (int j = 0; j < e[u].size(); ++j) {int v = e[u][j];if (dis[v] < dis[u] + 1)dis[v] = dis[u] + 1;in[v]--;if (in[v] == 0)q[tail++] = v;}}for (int i = 0; i <= n + 1; ++i)for (int j = 0; j <= n + 1; ++j) {d[i][j] = -INF;}for (int i = 0; i <= n + 1; ++i)e[i].clear();s[n + 1].d = INF;for (int i = n; i >= 0; --i) {//加边的时候注意不要加一些无用的边int mm = INF + 50;for (int j = i + 1; j <= n + 1; ++j) {if (mm <= s[j].d)continue;if (s[i].d <= s[j].d) {e[i].push_back(j);mm = min(s[j].d, mm);}}}d[0][0] = 0;for (int i = 0; i <= n + 1; ++i) {int u = q[i];for (int j = i; j <= n + 1; ++j) {int v = q[j];if (d[i][j] < 0)continue;for (int k = 0; k < e[u].size(); ++k) {//每次只从编号小的转移int x = id[e[u][k]];if (x == j) {d[x][j] = max(d[x][j], d[i][j]);}if (x < j) {d[x][j] = max(d[x][j], d[i][j] + 1);}if (x > j) {d[j][x] = max(d[j][x], d[i][j] + 1);}}}}printf("%d\n", d[n + 1][n + 1] - 1);}
}

这篇关于HDU 5406【费用流 或 dp+树状数组】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1102374

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :