【算法】网络流-最大流(dinic)

【题解】

飞船有可承载人数限制，地球为源点，月球为汇点，人像水流一样从以飞船上限为容量的边流向汇点。

人在各站点都面临着上船与否的选择，难以用DP解决最优策略，于是这样的取舍问题可以使用网络流。

其实主要是看数据范围。

构图思路：

由于我们要计算时间，所以使变量T从1开始循环直到运送完毕。

对于每个时间相应加边，从而可以不用在意周期问题。

时间T，对于每个点增加一个T*22+i的分点，并从(T-1)分点向T分点连一条容量为inf的边。

对于飞行路径从(T-1)*22+u向T*22+v连一条容量为p[i]的边。

构图完毕。

最后推一下极限情况下最长的时间，超过了输出0即可。

tot=1，不是0，不是2！

要加当前弧优化，速度会快很多(101ms→2ms)！

#include
      
       #include
       
        #include
        
         using namespace std;const int inf=0x3f3f3f3f;struct edge{
    int from,v,flow;}e[50010];int S=0,T,tot=1,first[4000],q[4000],a[25][25],cur[4000],d[4000],p[4000],n,m,k;void insert(int u,int v,int w){    tot++;e[tot].v=v;e[tot].flow=w;e[tot].from=first[u];first[u]=tot;    tot++;e[tot].v=u;e[tot].flow=0;e[tot].from=first[v];first[v]=tot;}bool bfs(){    memset(d,-1,sizeof(d));    int head=0,tail=1;q[0]=0;d[0]=0;    while(head!=tail)     {         int x=q[head++];if(head>=501)head=0;         for(int i=first[x];i;i=e[i].from)          if(d[e[i].v]==-1&&e[i].flow>0)           {               q[tail++]=e[i].v;if(tail>=501)tail=0;               d[e[i].v]=d[x]+1;           }     }    if(d[T*22+n+1]==-1)return 0;    return 1;}int dfs(int x,int a){    if(x==T*22+n+1||a==0)return a;    int flow=0,f;    for(int& i=cur[x];i;i=e[i].from)     if(d[e[i].v]==d[x]+1&&(f=dfs(e[i].v,min(a,e[i].flow)))>0)      {          e[i].flow-=f;          e[i^1].flow+=f;          flow+=f;          a-=f;          if(a==0)break;      }    return flow;}int main(){    scanf("%d%d%d",&n,&m,&k);    for(int i=1;i<=m;i++)     {         scanf("%d%d",&p[i],&a[i][0]);         for(int j=1;j<=a[i][0];j++)          {              scanf("%d",&a[i][j]);              if(a[i][j]==-1)a[i][j]=n+1;          }     }    for(T=1;T<=100;T++)     {         for(int i=0;i<=n+1;i++)          {              insert((T-1)*22+i,T*22+i,inf);          }         for(int i=1;i<=m;i++)          {              int u=(T-1)*22+a[i][(T-1)%a[i][0]+1];              int v=T*22+a[i][T%a[i][0]+1];              insert(u,v,p[i]);          }         while(bfs())          {              for(int i=0;i<=T*22+n+1;i++)cur[i]=first[i];              k-=dfs(0,inf);          }         if(k<=0){printf("%d",T);return 0;}     }    printf("0");    return 0;}