【题解】CTSC1999家园(网络流)

ゝ一世哀愁。 2021-11-18 01:20 254阅读 0赞

## CTSC1999家园 ##

建模方法类似我NOI2019网络同步赛我的T1写法\[【题解】[NOI2019Route\]（70分）][NOI2019Route_70]

问题的焦点是：空间时间载具。

*  考虑如何击破时间限制，可以对每个点关于每个时刻建立一个点，这样就实现一个点在两个时间互不干扰。由于时间是流淌的，所以从过去到现在连一条免费的\\(inf\\)边
 *  此时空间问题也就解决了，比较空间就是具体的节点。
 *  考虑载具，载具就相当于一个时刻在新建边的东西，我们直接枚举时间让他慢慢加点就好了。注意到载具总要从上个时间连接到这个时间，相当于虫洞？

下面这个图会非常清楚：

咕咕咕

写的话有点麻烦，模块化编程就稍微好写点。数据范围不超过100，不用怕MLE,TLE。

发现一种很好用的调试技巧，就是在add函数中输出fr to w 等等内容，按照这个提示建图就可以很快发现问题。

//@winlere #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long ll; inline int qr(){ register int ret=0,f=0; register char c=getchar(); while(c<48||c>57)f|=c==45,c=getchar(); while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar(); return f?-ret:ret; } const int maxn=5e4+5; struct E{ int to,nx,w; E(){to=nx=w=0;} E(const int&a,const int&b,const int&c){to=a;nx=b;w=c;} }e[maxn]; int head[maxn]; int last[maxn]; int lastlast[maxn]; int cnt=1; int n,m,k; int nodecnt; int S,T; const int inf=0x3f3f3f3f; inline void add(const int&fr,const int&to,const int&w,const int&f=1){ e[++cnt]=E(to,head[fr],w); head[fr]=cnt; if(f) add(to,fr,0,0); } queue < int > q; int d[maxn],cur[maxn]; inline bool bfs(){ for(register int t=1;t<=nodecnt;++t) d[t]=0,cur[t]=head[t]; d[S]=1;q.push(S); while(q.size()){ register int now=q.front(); q.pop(); //cout<<"now="<<now<<' '<<T<<endl; for(register int t=head[now];t;t=e[t].nx){ if(e[t].w>0&&d[e[t].to]==0){ d[e[t].to]=d[now]+1; q.push(e[t].to); } } } return d[T]; } int dfs(const int&now,int fl){ if(now==T||fl==0)return fl; register int ret=0; for(register int&t=cur[now];t;t=e[t].nx){ if(e[t].w>0&&d[e[t].to]==d[now]+1){ int d=dfs(e[t].to,min(e[t].w,fl)); e[t].w-=d;e[t^1].w+=d;ret+=d;fl-=d; } } return ret; } inline int dinic(){ register int ret=0; while(bfs()) ret+=dfs(S,inf); return ret; } int sh[205][205]; int siz[205]; int stay[205]; int cap[205]; inline void init(){ S=++nodecnt; T=++nodecnt; for(register int t=1;t<=n+2;++t) last[t]=++nodecnt; add(S,last[n+1],k); } inline void update(const int&now){ for(register int t=1;t<=n+2;++t) add(lastlast[t]=last[t],++nodecnt,inf),last[t]=nodecnt; for(register int t=1;t<=m;++t){ int la=stay[t]; int to=(stay[t]+1)%siz[t]; add(lastlast[sh[t][la]],last[sh[t][to]],cap[t]); stay[t]=to; } add(last[n+2],T,inf); } namespace binc{ int r[201]; int n; inline void init(int a){n=a;for(int t=1;t<=n;++t) r[t]=t;} int q(int a){return a==r[a]?a:r[a]=q(r[a]);} void j(int a,int b){r[q(a)]=q(b);} } int main(){ n=qr();m=qr();k=qr(); binc::init(n+2); for(register int t=1;t<=m;++t){ cap[t]=qr(); siz[t]=qr(); for(register int i=0;i<siz[t];++i){ sh[t][i]=qr(); if(sh[t][i]==0)sh[t][i]=n+1; if(sh[t][i]==-1)sh[t][i]=n+2; if(i)binc::j(sh[t][i],sh[t][i-1]); } } if(binc::q(n+1)!=binc::q(n+2)) return puts("0"),0; int timenow=0,sum=0,t1,cnt=0; init(); while(sum<k){ update(++timenow); t1=dinic(); sum+=t1; if(t1==0&&sum)++cnt; } printf("%d\n",timenow); return 0; }

转载于:https://www.cnblogs.com/winlere/p/11234637.html

[NOI2019Route_70]: https://www.cnblogs.com/winlere/p/11195100.html