题解 P2754 【星际转移问题】
这道题给出了太空船的飞行路线 相当于给出了空间站之间的关系 但是每一天飞船的位置都不一样 于是这样就启示我们以时间分层 因为总时间不确定 所以我们需要枚举答案
针对每一天建图 流量代表人数 某一时刻总流量>=k 那么就是答案
建模步骤:
1.建设源点S与地球连边 容量为inf
2.上一天的位置与这一天的位置连边 容量为载人数
3.因为人可以选择不上飞船 且空间站容量无限 所以上一天的这个位置与这一天这个位置连边 容量为inf
统计流量 >=k时即为答案
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define maxn 500
using namespace std;
int n,m,k,s,t,qhead,qtail,k1=-1,d=0,ans=0;
int cost[maxn+50],p[maxn+50],boat[maxn+50][maxn+50],dis[maxn*maxn+50];
int queue[maxn*maxn+50],f[maxn*maxn+50],head[maxn*maxn+50],c[maxn*maxn+50];
struct node{
int to,next,c;
}e[maxn*maxn+50];
void add(int u,int v,int c)
{
e[++k1].next=head[u],e[k1].to=v,e[k1].c=c,head[u]=k1;
e[++k1].next=head[v],e[k1].to=u,e[k1].c=0,head[v]=k1;
}
int find(int x)
{
if(x==f[x]) return x;
return f[x]=find(f[x]);
}
bool judge()
{
for(int i=1;i<=m;i++)
for(int j=1;j<p[i];j++)
{
int fx=find(boat[i][j]);
int fy=find(boat[i][j+1]);
if(fx!=fy) f[fx]=fy;
}
if(find(0)!=find(n+1)) return false;
return true;
}
bool bfs(int tail)
{
memset(dis,-1,sizeof(dis));
qhead=qtail=dis[t+1]=0;
queue[++qtail]=t+1;
while(qhead<qtail)
{
int p=queue[++qhead];
for(int i=head[p];i!=-1;i=e[i].next)
{
if(e[i].c && dis[e[i].to]==-1)
dis[e[i].to]=dis[p]+1,queue[++qtail]=e[i].to;
}
}
if(dis[tail]==dis[t+2]) return false;
return true;
}
int dfs(int u,int c)
{
int inc=0;
if(u==n+1+d*(n+2) || !c) return c;
for(int i=head[u];i!=-1;i=e[i].next)
if(dis[e[i].to]==dis[u]+1 && e[i].c)
{
int flow=dfs(e[i].to,min(e[i].c,c-inc));
e[i].c-=flow,e[i^1].c+=flow,inc+=flow;
if(inc==c) break;
}
if(!inc) dis[u]==-1;
return inc;
}
void Dinic(int d)
{
for(int i=0;i<=n+1;++i)
add(i+(d-1)*(n+2),i+d*(n+2),0xfff);
for(int i=1,b;i<=m;i++)
{
b=c[i]+1<=p[i]?c[i+1]:1;
add(boat[i][c[i]]+(d-1)*(n+2),boat[i][b]+d*(n+2),cost[i]);
c[i]=b;
}
while(bfs(n+1+d*(n+2))) ans+=dfs(t+1,0xfff);
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d%d%d",&n,&m,&k);t=maxn*maxn;
for(int i=0;i<=n;i++) f[i]=i;f[t]=t;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&cost[i],&p[i]);
for(int j=1;j<=p[i];j++)
{
scanf("%d",&boat[i][j]);
if(boat[i][j]==-1) boat[i][j]=n+1;
}
}
add(t+1,0,0xfff);
for(int i=1;i<=m;i++) c[i]=1;
while(1)
{
d++;Dinic(d);
if(ans>=k) {printf("%d",d);exit(0);}
if(d>=1010) {printf("0");exit(0);}//粗略的计算一下最大天数 当然保险也可以更大一点(别超时...)
}
return 0;
}