首页 > 代码库 > BZOJ 1930 Shoi2003 pacman 吃豆豆 费用流
BZOJ 1930 Shoi2003 pacman 吃豆豆 费用流
题目大意:给定一个平面上的一些点,吃豆先生从原点出发,只能向右或向上走,求两个吃豆先生最多吃到多少豆
每个点拆成两个,之间连一条流量为1,费用为1的边;
如果从一个点出发可以到达另一个点,就将前一个点的出点连向后一个点的入点
跑费用流。但是这样显然是会TLE的
如果i能到j,j能到k,那么显然无需连i->k这条边 这是一个剪枝
加了这个剪枝之后可能会WA 因此还要考虑一个点经过多次的情况
即每个点从入点向出点再连一条流量为1,费用为0的边
加了这个之后就能过了 剪枝不强 但是没有什么情况能把这个卡掉
MS是可以证明复杂度是根号级别的
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 4040 #define P1(x) (((x)<<1)-1) #define P2(x) ((x)<<1) #define S (n<<1|1) #define T (n+1<<1) #define INF 0x3f3f3f3f using namespace std; struct Point{ int x,y; bool operator < (const Point &p) const { if( x != p.x ) return x < p.x; return y < p.y; } friend istream& operator >> (istream& _,Point &p) { scanf("%d%d",&p.x,&p.y); return _; } }points[M]; struct abcd{ int to,f,cost,next; }table[4004004]; int head[M],tot=1; int n,ans,a[M]; void Add(int x,int y,int f,int cost) { table[++tot].to=y; table[tot].f=f; table[tot].cost=cost; table[tot].next=head[x]; head[x]=tot; } inline void Link(int x,int y,int f,int cost) { Add(x,y,f,cost); Add(y,x,0,-cost); } bool Edmonds_Karp() { static int q[65540],f[M],cost[M],from[M]; static unsigned short r,h; static bool v[M]; int i; memset(cost,0xef,sizeof cost); cost[S]=0;f[S]=INF;f[T]=0;q[++r]=S; while(r!=h) { int x=q[++h];v[x]=0; for(i=head[x];i;i=table[i].next) if(table[i].f&&cost[x]+table[i].cost>cost[table[i].to]) { cost[table[i].to]=cost[x]+table[i].cost; f[table[i].to]=min(f[x],table[i].f); from[table[i].to]=i; if(!v[table[i].to]) v[table[i].to]=1,q[++r]=table[i].to; } } if(!f[T]) return false; ans+=f[T]*cost[T]; for(i=from[T];i;i=from[table[i^1].to]) table[i].f-=f[T],table[i^1].f+=f[T]; return true; } int main() { int i,j; cin>>n; for(i=1;i<=n;i++) cin>>points[i]; sort(points+1,points+n+1); for(i=1;i<=n;i++) { a[i]=points[i].y; int temp=-1; Link(0,P1(i),1,0); Link(P2(i),T,1,0); Link(P1(i),P2(i),1,1); Link(P1(i),P2(i),1,0); for(j=i-1;j;j--) if(a[j]<=a[i]&&a[j]>temp) temp=a[j],Link(P2(j),P1(i),2,0); /* for(j=1;j<i;j++) if(a[j]<=a[i]) Link(P2(j),P1(i),1,0); */ } Link(S,0,2,0); while( Edmonds_Karp() ); cout<<ans<<endl; return 0; }
BZOJ 1930 Shoi2003 pacman 吃豆豆 费用流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。