题目背景

none!

题目描述

由于人类对自然资源的消耗，人们意识到大约在 2300 年之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。

现有 n 个太空站位于地球与月球之间，且有 m 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而每艘太空船 i 只可容纳 H[i]个人。每艘太空船将周期性地停靠一系列的太空站，例如：(1，3，4)表示该太空船将周期性地停靠太空站 134134134…。每一艘太空船从一个太空站驶往任一太空站耗时均为 1。人们只能在太空船停靠太空站(或月球、地球)时上、下船。

初始时所有人全在地球上，太空船全在初始站。试设计一个算法，找出让所有人尽快地全部转移到月球上的运输方案。

对于给定的太空船的信息，找到让所有人尽快地全部转移到月球上的运输方案。

输入输出格式

输入格式：

第 1 行有 3 个正整数 n（太空站个数），m（太空船个数）和 k（需要运送的地球上的人的个数）。其中 n<=13 m<=20, 1<=k<=50。

接下来的 m 行给出太空船的信息。第 i+1 行说明太空船 pi。第 1 个数表示 pi 可容纳的人数 Hpi；第 2 个数表示 pi 一个周期停靠的太空站个数 r，1<=r<=n+2；随后 r 个数是停靠的太空站的编号(Si1,Si2,…,Sir)，地球用 0 表示，月球用-1 表示。

时刻 0 时，所有太空船都在初始站，然后开始运行。在时刻 1，2，3…等正点时刻各艘太空船停靠相应的太空站。人只有在 0,1,2…等正点时刻才能上下太空船。

输出格式：

程序运行结束时，将全部人员安全转移所需的时间输出。如果问题

无解，则输出 0。

解题思路：

假如说告诉你多少天，问转移人口，那是不是会好一些，

按时间分层，不同层相同点间按照时间方向建$inf$的边，

跑一边最大流，源点是0时刻的地球，汇点是T时刻的月球。

最大流就是人口。

所以枚举判断好了。

代码：

 #include<queue>

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<algorithm>

 const int oo=0x3f3f3f3f;

 struct pnt{

     int hd;

     int lyr;

     int now;

 }p[];

 struct ent{

     int twd;

     int lst;

     int vls;

 }e[];

 int cnt;

 int n,m,k;

 int s,t;

 int size;

 int H[];

 int fa[];

 std::queue<int>Q;

 std::vector<int>st[];

 void ade(int f,int t,int v)

 {

     cnt++;

     e[cnt].twd=t;

     e[cnt].vls=v;

     e[cnt].lst=p[f].hd;

     p[f].hd=cnt;

     return ;

 }

 bool Bfs(void)

 {

     while(!Q.empty())

         Q.pop();

     for(int i=;i<=size;i++)

         p[i].lyr=;

     p[s].lyr=;

     Q.push(s);

     while(!Q.empty())

     {

         int x=Q.front();

         Q.pop();

         for(int i=p[x].hd;i;i=e[i].lst)

         {

             int to=e[i].twd;

             if(p[to].lyr==&&e[i].vls>)

             {

                 p[to].lyr=p[x].lyr+;

                 if(to==t)

                     return true;

                 Q.push(to);

             }

         }

     }

     return false;

 }

 int Dfs(int x,int fll)

 {

     if(x==t)

         return fll;

     for(int& i=p[x].now;i;i=e[i].lst)

     {

         int to=e[i].twd;

         if(p[to].lyr==p[x].lyr+&&e[i].vls>)

         {

             int ans=Dfs(to,std::min(fll,e[i].vls));

             if(ans>)

             {

                 e[i].vls-=ans;

                 e[((i-)^)+].vls+=ans;

                 return ans;

             }

         }

     }

     return ;

 }

 int Dinic(void)

 {

     int ans=;

     while(Bfs())

     {

         for(int i=;i<=size;i++)

             p[i].now=p[i].hd;

         int dlt;

         while(dlt=Dfs(s,oo))

             ans+=dlt;

     }

     return ans;

 }

 int finf(int x)

 {

     return fa[x]==x?x:fa[x]=finf(fa[x]);

 }

 int main()

 {

 //    freopen("a.in","r",stdin);

     scanf("%d%d%d",&n,&m,&k);

     for(int i=;i<=n+m+;i++)fa[i]=i;

     for(int i=;i<=m;i++)

     {

         scanf("%d",&H[i]);

         int tmp;

         scanf("%d",&tmp);

         for(int j=;j<=tmp;j++)

         {

             int tl;

             scanf("%d",&tl);

             if(tl==)tl=n+;

             if(tl==-)tl=n+;

             st[i].push_back(tl);

             int f1=finf(tl);

             int f2=finf(n++i);

             if(f1!=f2)

                 fa[f1]=f2;

         }

     }

     if(finf(n+)!=finf(n+))

     {

         printf("%d\n",);

         return ;

     }

     s=n+;

     int N;

     int popu=;

     for(N=;;N++)

     {

         if(N)

         {

             for(int i=;i<=n+m+;i++)

             {

                 ade((N-)*(n+m+)+i,N*(n+m+)+i,oo);

                 ade(N*(n+m+)+i,(N-)*(n+m+)+i,);

             }

         }

         size=(N+)*(n+m+);

         t=N*(n+m+)+n+;

         for(int i=;i<=m;i++)

         {

             int tp=st[i][N%st[i].size()];

             if(tp!=n+)

             {

                 ade(N*(n+m+)+n++i,N*(n+m+)+tp,H[i]);

                 ade(N*(n+m+)+tp,N*(n+m+)+n++i,);

             }

             if(tp!=n+)

             {

                 ade(N*(n+m+)+tp,N*(n+m+)+n++i,H[i]);

                 ade(N*(n+m+)+n++i,N*(n+m+)+tp,);

             }

         }

         popu+=Dinic();

         if(popu<k);else break;

     }

     printf("%d\n",N);

     return ;

 }

巴特西

LuoguP2754 [CTSC1999]家园(分层图，最大流)

题目背景

题目描述

输入输出格式

解题思路：

最新文章

热门文章