【题意】
由于人类对自然资源的消耗， 人们意识到大约在 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掉的。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
#define Maxn 4100
#define INF 0xfffffff struct node
{
int x,y,f,o,next;
}t[Maxn*];int len;
int first[Maxn];
int n,m,k; int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} void ins(int x,int y,int f)
{
t[++len].x=x;t[len].y=y;t[len].f=f;
t[len].next=first[x];first[x]=len;t[len].o=len+;
t[++len].x=y;t[len].y=x;t[len].f=;
t[len].next=first[y];first[y]=len;t[len].o=len-;
} int st,ed;
queue<int > q;
int dis[Maxn];
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-,sizeof(dis));
q.push(st);dis[st]=;
while(!q.empty())
{
int x=q.front();
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]==-)
{
dis[y]=dis[x]+;
q.push(y);
}
}
q.pop();
}
if(dis[ed]==-) return ;
return ;
} int ffind(int x,int flow)
{
if(x==ed) return flow;
int now=;
for(int i=first[x];i;i=t[i].next) if(t[i].f>)
{
int y=t[i].y;
if(dis[y]==dis[x]+)
{
int a=ffind(y,mymin(flow-now,t[i].f));
t[i].f-=a;
t[t[i].o].f+=a;
now+=a;
}
if(now==flow) break;
}
if(now==) dis[x]=-;
return now;
} void output()
{
for(int i=;i<=len;i+=)
printf("%d->%d %d\n",t[i].x,t[i].y,t[i].f);
printf("\n");
} int max_flow()
{
int ans=;
while(bfs())
{
ans+=ffind(st,INF);
}
return ans;
} int hp[],rl[][],cnt=,add;
vector<int > num[]; bool check(int x)
{
for(int i=;i<=n;i++) num[i].push_back(++cnt);
num[].push_back();num[n+].push_back();
for(int i=;i<=m;i++)
{
int y=rl[i][(x-)%rl[i][]+],z=rl[i][x%(rl[i][])+];
if(z==||y==n+) continue;
y=num[y][x];z=num[z][x+];
ins(y,z,hp[i]);
}
for(int i=;i<=n;i++) ins(num[i][x],num[i][x+],INF);
int now=max_flow();
add+=now;
return add>=k;
} int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=m;i++)
{
scanf("%d%d",&hp[i],&rl[i][]);
for(int j=;j<=rl[i][];j++)
{
scanf("%d",&rl[i][j]);
// printf("%d\n",rl[i][j]);
if(rl[i][j]==-) rl[i][j]=n+;
}
}
for(int i=;i<=m;i++) num[i].clear();
for(int i=;i<=n+;i++) num[i].push_back();//
int ans=;st=;ed=;
for(int i=;i<=n;i++) num[i].push_back(++cnt);
num[].push_back();num[n+].push_back();
add=;
while()
{
ans++;
if(check(ans)) {printf("%d\n",ans);break;}
if(ans>) {printf("0\n");break;}
} return ;
}
表示边也不知道要开多少，就开了好大好大。。
2016-11-04 22:04:54
对了，这里有个有点良心的网站可以交24题，然而，还是没有SPJ。。。