【BZOJ1930】【SHOI2003】吃豆豆

初见杀……

原题：

两个PACMAN吃豆豆。一开始的时候，PACMAN都在坐标原点的左下方，豆豆都在右上方。PACMAN走到豆豆处就会吃掉它。PACMAN行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。请你帮这两个PACMAN计算一下，他们俩加起来最多能吃掉多少豆豆。

N < = 2000

一眼秒掉，拆点费用流

然后发现内存64M？？？减少边的数组，提交，RE……

看chty的题解，更换建图方式，减少边数，提交，WA……

然后我的上午没了

【BZOJ1930】【SHOI2003】吃豆豆

解题思路很简单，拆点费用流即可，关键就在减少边数上

先按x第一优先级y第二优先级升序排序，然后对于每个点i从i+1往后扫，同时记录一个max（初值为oo），对于某个扫到的点j，如果a[j]>=a[i]且a[j]<max，就连边并max=a[j]

然后对于每个拆开的点中间连费用为1的边基础上再连费用为0的边，这样做是为了配合上面的建图方式使得前面的点能跳过这个点扫到后面的点

注意一定要连费用为0，否则后果就是直接被干掉一个上午/下午/晚上

主要原因还是因为看到这种建图方式后没有深刻理解就直接写上去了，导致最后没有连出费用为0的边

心好累，实在看不懂怎么建图就看代码把，注意不要忘了费用为0的边

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 #define ll long long
 8 const int oo=1000000000;
 9 ll rd(){ll z=0,mk=1;  char ch=getchar();
10     while(ch<'0'||ch>'9'){if(ch=='-')mk=-1;  ch=getchar();}
11     while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}
12     return z*mk;
13 }
14 struct dcd{ll x,y;}a[21000];
15 bool cmp(dcd x,dcd y){  return (x.x==y.x)?(x.y<y.y):(x.x<y.x);}
16 //bool cmp(dcd x,dcd y){  return x.x<y.x;}
17 struct ddd{int nxt,y,v,rvs,c;}e[810000];  int lk[4100],ltp=0;
18 inline void ist(int x,int y,int z,int _cst){
19     e[++ltp].nxt=lk[x],lk[x]=ltp,e[ltp].y=y,e[ltp].v=z,e[ltp].rvs=ltp+1,e[ltp].c=_cst;
20     e[++ltp].nxt=lk[y],lk[y]=ltp,e[ltp].y=x,e[ltp].v=0,e[ltp].rvs=ltp-1;e[ltp].c=-_cst;
21 }
22 int n;  int s,t,ss;
23 int lst[4100],lst_e[4100];
24 int dst[4100];
25 int q[810000],hd=0,tl=0,qt=800000;  bool vstd[4100];
26 bool spfa(){
27     memset(dst,-1,sizeof(dst));
28     q[hd=1]=s;  tl=0;  vstd[s]=true;  dst[s]=0;
29     //for(int k=1;k<=hd;++k){
30     while(tl!=hd){
31         int k=tl=(tl==qt ? 1 : tl+1);
32         for(int i=lk[q[k]];i;i=e[i].nxt)
33             if(e[i].v && dst[q[k]]+e[i].c>dst[e[i].y]){
34                 dst[e[i].y]=dst[q[k]]+e[i].c;
35                 lst[e[i].y]=q[k],lst_e[e[i].y]=i;
36                 if(!vstd[e[i].y])  q[hd=(hd==qt ? 1 : hd+1)]=e[i].y,vstd[e[i].y]=true;
37             }
38         vstd[q[k]]=false;
39     }
40     return dst[t]>0;
41 }
42 int cstflw(){
43     int bwl=0,mnflw=oo;
44     while(spfa()){
45         mnflw=oo;
46         for(int i=t;i!=s;i=lst[i])  mnflw=min(mnflw,e[lst_e[i]].v);
47         for(int i=t;i!=s;i=lst[i]){
48             bwl+=mnflw*e[lst_e[i]].c;
49             //cout<<lst[i]<<" "<<i<<" "<<e[lst_e[i]].c<<endl;
50             e[lst_e[i]].v-=mnflw,e[e[lst_e[i]].rvs].v+=mnflw;
51         }
52     }
53     return bwl;
54 }
55 int main(){//freopen("ddd.in","r",stdin);
56     //freopen("ddd.out","w",stdout);
57     memset(vstd,0,sizeof(vstd));
58     cin>>n;  s=0,t=n+n+1,ss=t+1;
59     for(int i=1;i<=n;++i)  a[i].x=rd(),a[i].y=rd();
60     sort(a+1,a+n+1,cmp);
61     //for(int i=1;i<=n;++i)  cout<<a[i].x<<" "<<a[i].y<<endl;
62     for(int i=1;i<=n;++i){
63         int mx=oo;
64         for(int j=i+1;j<=n;++j)
65             if(a[j].y>=a[i].y && a[j].y<=mx)  ist(i+n,j,oo,0),mx=a[j].y;
66             //if(a[j].y>=a[i].y && a[j].x>=a[i].x)  ist(i+n,j,oo,0);
67         ist(ss,i,oo,0),ist(i+n,t,oo,0),ist(i,i+n,1,1),ist(i,i+n,1,0);
68     }
69     ist(s,ss,2,0);
70     cout<<cstflw()<<endl;
71     return 0;
72 }

View Code

【BZOJ1930】【SHOI2003】吃豆豆

相关推荐