bzoj 2465 小球-白红宇

bzoj 2465 小球

阅读量：4581 次

发布时间：2019-06-09

本文共 2490 字，大约阅读时间需要 8 分钟。

题目大意：

给定n个不同颜色的球，每个球都有一个分数，同时有m个瓶子，每个瓶子都有固定的容量

必须把球放到瓶子里面计算最多能放多少个球到这些瓶子里

思路：

开始想的是费用流

超级源向每个球连一条容量为1，费用为球的分数的边

每个瓶子和它可以装下的球连一条容量为1，费用为0的边

每个瓶子和汇点连一条容量为瓶的容量，费用为0的边

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              10 #define ll long long11 #define inf 213906214312 #define MAXN 50013 using namespace std;14 inline int read()15 {16 int x=0,f=1;char ch=getchar();17 while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}18 while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();19 return x*f;20 }21 int n,m,s,t,a[MAXN];22 ll ans;23 struct ZKW24 {25 int fst[MAXN],to[MAXN*MAXN],nxt[MAXN*MAXN],val[MAXN*MAXN],cos[MAXN*MAXN],cnt;26 int dis[MAXN],vis[MAXN],q[MAXN];27 void mem() {ans=0,cnt=0;memset(fst,0xff,sizeof(fst));}28 void add(int u,int v,int w,int c) {nxt[cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w,cos[cnt++]=c;}29 int spfa()30 {31 memset(vis,0,sizeof(vis));32 memset(dis,127,sizeof(dis));33 int l=1,r=0;34 q[++r]=t,dis[t]=0,vis[t]=1;35 while(l<=r)36 {37 int x=q[l++];38 for(int i=fst[x];i!=-1;i=nxt[i])39 {40 if(val[i^1] && dis[to[i]]>dis[x]-cos[i])41 {42 dis[to[i]]=dis[x]-cos[i];43 if(!vis[to[i]]) q[++r]=to[i],vis[to[i]]=1;44 }45 }46 vis[x]=0;47 }48 return dis[s]
               
                >n>>m)82 {83 if(!n&&!m) return 0;84 Z.mem();85 s=0,t=n+m+1;86 for(int i=1;i<=n;i++) {a[i]=read();Z.add(s,i,1,-a[i]);Z.add(i,s,0,a[i]);}87 for(int j=1;j<=m;j++)88 {89 g=read(),h=read();90 for(int i=1;i<=n;i++) 91 if(h>=a[i]) {Z.add(i,n+j,1,0);Z.add(n+j,i,0,0);}92 Z.add(n+j,t,g,0);Z.add(t,n+j,0,0);93 }94 Z.solve();95 }96 }

View Code

棒神写的费用流没T 还是我太弱了 %%%棒神

然后发现有个贪心就是使每个球尽可能价值最大，A了

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              10 #define ll long long11 #define inf 213906214312 #define MAXN 22013 using namespace std;14 inline int read()15 {16 int x=0,f=1;char ch=getchar();17 while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}18 while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();19 return x*f;20 }21 int n,m,a[MAXN];22 struct data23 {24 int q,c;25 bool operator < (const data &x)const26 {27 return q
               
                
                 =a[i]) b[j].c--,ans++,res+=a[i];45 }46 printf("%d %d\n",ans,res);47 }48 }