首页 > 代码库 > Shoot the Bullet

Shoot the Bullet

2024-07-20 11:27:55   211人阅读

zoj3229:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3442

题意：一个摄影师，在n天内给m个女神拍照。每个女神至少要拍Gi张照片，每一天只能给Ci个女神照相，每一天只能只能拍Di张照片，并且每个女神每天被拍的数量在[l,r]之间。问是否存在一种方案，满足条件，如果满足，最多可以照多少照片。

题解：这是一条有源汇的有上下界的最大流。首先源点s，t，源点和每一天i建立一边，上界为Di，下界为0，每个女神和t建立一边，上界是无穷，下界是Gi，因为上界是无穷大，所以下界等同为0，然后是每一天与对应的女神之间就是流量范围是[l,r],这里就可以转化成有上下界的流量处理，最后t-->s建立一边，容量是INF，这样就转化成无汇源的可行流。接下就是设超级源点ss，超级会点tt,把上面的图按照可行流的求解方式来求解。如果所有ss的出边都是满流，则有可行解。然后再跑一边最大流，此时源点时s，t，这里不再是超级源点ss，和会点tt。

  1 #include<iostream>  2 #include<cstring>  3 #include<cstdio>  4 #include<algorithm>  5 #include<queue>  6 using namespace std;  7 #define INF 1000000000  8 const int N=1510;  9 struct Node { 10     int c; 11     int f; 12 }map[N][N]; 13 int sx,ex,n,m; 14 int pre[N]; 15 int du[N],down[N][N]; 16 bool BFS(int x) { //BFS搜索层次网络 17     memset(pre,0,sizeof(pre)); 18     queue< int > Q; 19     Q.push(sx); 20     pre[sx]=1; 21     while(!Q.empty()) { 22         int d=Q.front(); 23         Q.pop(); 24         for(int i=1; i<=x; i++) { 25             if(!pre[i]&&map[d][i].c-map[d][i].f) { 26                 pre[i]=pre[d]+1; 27                 Q.push(i); 28             } 29         } 30     } 31     return pre[ex]!=0; 32 } 33 int dinic(int pos,int flow,int x) { //pos是顶点号，flow是当前顶点所能得到的流量,一次dinic只能求出一次增加的流量， 34     int f=flow; 35     if(pos==ex) 36         return flow; 37     for(int i=1; i<=x; i++) { 38         if(map[pos][i].c-map[pos][i].f&&pre[pos]+1==pre[i]) { 39             int a=map[pos][i].c-map[pos][i].f; 40             int t=dinic(i,min(a,flow),x); 41             map[pos][i].f+=t; 42             map[i][pos].f-=t; 43             flow-=t; 44             if(flow<=0)break; 45             //我最开始就是这里没弄明白，我不明白为什么要此顶点得到的流量减去改变量； 46             //答案就在下面的  return f-flow; 47         } 48     } 49     if(f-flow<=0)pre[pos]=-1; 50     return f-flow;//其实这里返回给他前一层的就是这个t;因为t在层函数里面都有，所以所过避免重复就写成这样； 51 } 52 int solve(int x){ 53     int sum=0; 54     while(BFS(x)) { 55         sum+=dinic(sx,INF,x); 56     } 57     return sum; 58 } 59 int main() { 60     int u,v,w,t1,t2,t3; 61     while(~scanf("%d%d",&n,&m)) { 62         int s=m+n+1,t=s+1; 63         sx=t+1,ex=sx+1; 64         memset(map,0,sizeof(map)); 65         memset(du,0,sizeof(du)); 66         memset(down,-1,sizeof(down)); 67         for(int i=1;i<=m; i++) { 68             scanf("%d",&w); 69             du[i]-=w; 70             du[t]+=w; 71             map[i][t].c+=INF; 72         } 73         for(int i=1;i<=n;i++){ 74           scanf("%d%d",&u,&v); 75            map[s][i+m].c+=v; 76            while(u--){ 77                scanf("%d%d%d",&t1,&t2,&t3); 78                du[t1+1]+=t2; 79                du[i+m]-=t2; 80                down[i+m][t1+1]=t2; 81                map[i+m][t1+1].c+=(t3-t2); 82            } 83         } 84         map[t][s].c=INF; 85         int sum=0; 86        for(int i=1;i<=t;i++){ 87           if(du[i]>0){ 88                 map[sx][i].c+=du[i]; 89                 sum+=du[i]; 90           } 91           else{ 92             map[i][ex].c+=(-du[i]); 93           } 94        } 95        if(solve(n+m+4)!=sum)puts("-1"); 96        else{ 97           sx=s,ex=t; 98           printf("%d\n",solve(n+m+2)); 99           for(int i=m+1;i<=n+m;i++){100               for(int j=1;j<=m;j++){101                  if(down[i][j]>=0){102                     printf("%d\n",map[i][j].f+down[i][j]);103                  }104               }105            }106         }107      puts("");108     }109     return 0;110 }
View Code

 

Shoot the Bullet


联系
我们