P2754 [CTSC1999]家园 / 星际转移问题

星际转移问题"/>

P2754 [CTSC1999]家园 / 星际转移问题

题目

题目

思路

拆点……
拆到怀疑人生的破题目
code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int n,m,s,t,x[13*20*5+20],y,tot=2,head[1000005],dep[1000005],l,r,u[1000005],fa[1000005],r2;
long long w,ans;
long long mn(long long x,long long y)
{return (x>y?y:x);
}
struct f{int to,net;long long w;
} a[1001005];
int find(int x)
{if (fa[x]==0) return x;else return fa[x]=find(fa[x]);
}
void add(int x,int y,long long w)
{a[tot].to=y,a[tot].w=w,a[tot]=head[x],head[x]=tot++;if (find(x)!=find(y)) fa[find(x)]=find(y);return;
}
bool bfs()
{memset(dep,0,sizeof(dep));l=0,r=0;u[r++]=s;dep[s]=1;while (l<r){r2=r;for (int i=l;i<r;i++){for (int j=head[u[i]];j;j=a[j]){if (a[j].w!=0&&dep[a[j].to]==0){u[r2++]=a[j].to;dep[a[j].to]=dep[u[i]]+1;}}}l=r,r=r2;}return dep[t];
}
long long dfs(int d,long long in)
{if (d==t) return in;long long out=0;int uw=dep[d]+1;for (int j=head[d];j&&in;j=a[j]){if (a[j].w==0||dep[a[j].to]!=uw) continue;long long s=dfs(a[j].to,mn(in,a[j].w));out+=s,in-=s;a[j].w-=s,a[j^1].w+=s;}if (out==0){dep[d]=0;}return out;
}
int k;
int main()
{scanf("%d%d%d",&n,&m,&k);s=1000004,t=1000003;for (int i=1;i<=n+2;i++){for (int j=13*20*5+19;j>=1;j--){add(i+(j-1)*(n+2),i+j*(n+2),1e17);add(i+j*(n+2),i+(j-1)*(n+2),0);}}for (int i=1;i<=m;i++){int zz;scanf("%lld%d%d",&w,&zz,&x[0]);x[0]+=2;for (int j=1;j<zz;j++){scanf("%d",&x[j]);x[j]+=2+(n+2)*j;add(x[j-1],x[j],w);add(x[j],x[j-1],0);}for (int j=zz;j<13*20+20;j++){x[j]=x[j-zz]+(n+2)*zz;add(x[j-1],x[j],w);add(x[j],x[j-1],0);}}for (int i=1;i<13*20*5+20;i++){add(s,(i-1)*(n+2)+2,1e17);add((i-1)*(n+2)+2,s,0);add((i-1)*(n+2)+1,t,1e17);add(t,(i-1)*(n+2)+1,0);ans=0;while (bfs()){ans+=dfs(s,1e30);if (ans>=k) break;}if (ans>=k){cout<<i-1;return 0;}for (int o=2;o<tot;o+=2){a[o].w+=a[o+1].w;a[o+1].w=0;}}cout<<0<<endl;return 0;
}