【网络流24题】No. 13 星际转移问题（网络判定最大流）-白红宇

【网络流24题】No. 13 星际转移问题（网络判定最大流）

阅读量：5025 次

发布时间：2019-06-12

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

【题意】

　　由于人类对自然资源的消耗，人们意识到大约在 2300 年之后，地球就不能再居住了。

于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是， 2177 年冬由于未

知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。现有 n 个太空站

位于地球与月球之间，且有 m 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限

多的人，而每艘太空船 i 只可容纳 H[i]个人。每艘太空船将周期性地停靠一系列的太空站，

例如： (1， 3， 4)表示该太空船将周期性地停靠太空站 134134134…。每一艘太空船从一个太

空站驶往任一太空站耗时均为 1。人们只能在太空船停靠太空站(或月球、地球)时上、下船。

初始时所有人全在地球上，太空船全在初始站。试设计一个算法，找出让所有人尽快地全部

转移到月球上的运输方案。

输入文件示例
input.txt
2 2 1
1 3 0 1 2
1 3 1 2 –1

输出文件示例
output.txt
5

【分析】

　　这题跟LA2957 很像。应该是很经典的模型。

　　很容易想到要二分然后判定，但其实枚举更好，按顺序枚举的话，可以不重新建图，直接加边，继续跑，前面的题目中我也打过了的。

　　然后拆点，假设枚举到d天，那么每个站就有d个点，然后如果有一个太空船第d天从u->v，那么u(d)->v(d+1),容量为太空船容量。即图上的点表示太空站，图上的边表示太空船。

　　然后跑最大流。

　　其实有点难打啊，这一题。我还用了vector，然后不连通其实要特判，不过我是加了上边界A掉的。

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #include
               10 using namespace std; 11 #define Maxn 4100 12 #define INF 0xfffffff 13 14 struct node 15 { 16 int x,y,f,o,next; 17 }t[Maxn*1010];int len; 18 int first[Maxn]; 19 int n,m,k; 20 21 int mymin(int x,int y) { return x
               
                y?x:y;} 23 24 void ins(int x,int y,int f) 25 { 26 t[++len].x=x;t[len].y=y;t[len].f=f; 27 t[len].next=first[x];first[x]=len;t[len].o=len+1; 28 t[++len].x=y;t[len].y=x;t[len].f=0; 29 t[len].next=first[y];first[y]=len;t[len].o=len-1; 30 } 31 32 int st,ed; 33 queue
                
                  q; 34 int dis[Maxn]; 35 bool bfs() 36 { 37 while(!q.empty()) q.pop(); 38 memset(dis,-1,sizeof(dis)); 39 q.push(st);dis[st]=0; 40 while(!q.empty()) 41 { 42 int x=q.front(); 43 for(int i=first[x];i;i=t[i].next) if(t[i].f>0) 44 { 45 int y=t[i].y; 46 if(dis[y]==-1) 47 { 48 dis[y]=dis[x]+1; 49 q.push(y); 50 } 51 } 52 q.pop(); 53 } 54 if(dis[ed]==-1) return 0; 55 return 1; 56 } 57 58 int ffind(int x,int flow) 59 { 60 if(x==ed) return flow; 61 int now=0; 62 for(int i=first[x];i;i=t[i].next) if(t[i].f>0) 63 { 64 int y=t[i].y; 65 if(dis[y]==dis[x]+1) 66 { 67 int a=ffind(y,mymin(flow-now,t[i].f)); 68 t[i].f-=a; 69 t[t[i].o].f+=a; 70 now+=a; 71 } 72 if(now==flow) break; 73 } 74 if(now==0) dis[x]=-1; 75 return now; 76 } 77 78 void output() 79 { 80 for(int i=1;i<=len;i+=2) 81 printf("%d->%d %d\n",t[i].x,t[i].y,t[i].f); 82 printf("\n"); 83 } 84 85 int max_flow() 86 { 87 int ans=0; 88 while(bfs()) 89 { 90 ans+=ffind(st,INF); 91 } 92 return ans; 93 } 94 95 int hp[110],rl[110][110],cnt=2,add; 96 vector
                 
                   num[110]; 97 98 bool check(int x) 99 {100 for(int i=1;i<=n;i++) num[i].push_back(++cnt);101 num[0].push_back(1);num[n+1].push_back(2);102 for(int i=1;i<=m;i++)103 {104 int y=rl[i][(x-1)%rl[i][0]+1],z=rl[i][x%(rl[i][0])+1];105 if(z==0||y==n+1) continue;106 y=num[y][x];z=num[z][x+1];107 ins(y,z,hp[i]);108 }109 for(int i=1;i<=n;i++) ins(num[i][x],num[i][x+1],INF);110 int now=max_flow();111 add+=now;112 return add>=k;113 }114 115 int main()116 {117 scanf("%d%d%d",&n,&m,&k);118 for(int i=1;i<=m;i++)119 {120 scanf("%d%d",&hp[i],&rl[i][0]);121 for(int j=1;j<=rl[i][0];j++)122 {123 scanf("%d",&rl[i][j]);124 // printf("%d\n",rl[i][j]);125 if(rl[i][j]==-1) rl[i][j]=n+1;126 }127 }128 for(int i=1;i<=m;i++) num[i].clear();129 for(int i=0;i<=n+1;i++) num[i].push_back(0);//00000130 int ans=0;st=1;ed=2;131 for(int i=1;i<=n;i++) num[i].push_back(++cnt);132 num[0].push_back(1);num[n+1].push_back(2);133 add=0;134 while(1)135 {136 ans++;137 if(check(ans)) {printf("%d\n",ans);break;}138 if(ans>100) {printf("0\n");break;}139 }140 141 return 0;142 }

View Code

表示边也不知道要开多少，就开了好大好大。。

2016-11-04 22:04:54

对了，这里有个有点良心的网站可以交24题，然而，还是没有SPJ。。。

转载于:https://www.cnblogs.com/Konjakmoyu/p/6031836.html

你可能感兴趣的文章