@[MichaelWong](/user/765446) 一般来说是总的点数再去加1
by bamboo1030 @ 2023-06-23 08:03:36
@[bamboo123](/user/369181) 理论上这个图的点数应该是 $n \times (day+1) -1,$ 然而这好像不太行……
by MichaelWong @ 2023-06-23 08:15:03
我甚至尝试过在连边时计算总点数，但是总点数 +1 好像 8 太行……
by MichaelWong @ 2023-06-23 08:15:53
@[MichaelWong](/user/765446) 给我看一眼那个的代码
by bamboo1030 @ 2023-06-23 08:17:08
@[bamboo123](/user/369181)
动态判断点数：
```cpp
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii std::pair<int,int>
#define fsp(x) std::fixed<<std::setprecision(x)
#define forE(u) for(int p=head[u],v=to[p];p;p=next[p],v=to[p])
const int N=35,M=3e4+5,inf=1064;
int n,m,k,s,t,h[N],r[N],S[N][N],tot=0;
struct network {
int cnt=1,top=1,have[M],head[M],to[M<<1],next[M<<1],lim[M<<1];
inline void add(int u,int v,int w) {
if(!have[u]) have[u]=1,++top;
if(!have[v]) have[v]=1,++top;
to[++cnt]=v,lim[cnt]=w,next[cnt]=head[u],head[u]=cnt;
to[++cnt]=u,lim[cnt]=0,next[cnt]=head[v],head[v]=cnt;
}
int dis[M],cur[M],gap[M];
int dfs(int u,int res) {
if(u==t) return res;
int flow=0;
for(int &p=cur[u];p&&res;p=next[p]) {
int c=std::min(res,lim[p]),v=to[p];
if(dis[v]==dis[u]-1&&c) { int fl=dfs(v,c); flow+=fl,res-=fl,lim[p^1]+=fl,lim[p]-=fl; }
if(!res) return flow;
}
if(--gap[dis[u]]==0) dis[s]=n;
return ++gap[++dis[u]],flow;
}
int maxflow() {
int flow=0; std::queue<int> q;
memset(dis,-1,sizeof dis);
gap[dis[t]=0]=1,q.push(t);
while(!q.empty()) {
int u=q.front(); q.pop();
forE(u) if(dis[v]==-1&&!lim[p]) ++gap[dis[v]=dis[u]+1],q.push(v);
}
while(dis[s]<top) { memcpy(cur,head,sizeof head); flow+=dfs(s,inf); }
return flow;
}
} f;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
std::cin>>n>>m>>k; s=1,t=0;
for(int i=1;i<=m;++i) {
std::cin>>h[i]>>r[i];
for(int j=0;j<r[i];++j) std::cin>>S[i][j];
}
for(int day=1;day<=1000;++day) {
int base=day*n+1;
for(int i=1;i<=n;++i) f.add(base-n+i,base+i,inf);
for(int i=1;i<=m;++i) {
int pre=S[i][(day-1)%r[i]],cur=S[i][day%r[i]];
pre+=pre>0?base-n:1,cur+=cur>0?base:1;
f.add(pre,cur,h[i]);
}
if((tot+=f.maxflow())>=k) return std::cout<<day<<'\n' && 0;
}
std::cout<<"0\n";
return 0;
}
```
甚至样例都过不去……好像死循环了
计算理论总点数就是把主程序里的 `top=std::min(day+1,300);` 改成 `top=(day+1)*n-1`
by MichaelWong @ 2023-06-23 08:22:36
@[MichaelWong](/user/765446) dfs里面也要改啊
by bamboo1030 @ 2023-06-23 08:37:01
@[bamboo123](/user/369181) 啊，感谢大佬，我赋的 `top=(day+1)*n+2;`，把 dfs 里面也改了，没有问题了，现在就 #11 那个 hack 数据过不了，是 T，我本地跑了一下，9s 左右qaq, 您知道什么原因吗
by MichaelWong @ 2023-06-23 09:18:33
@[MichaelWong](/user/765446) 不太知道，我也没跑过，感觉也不知道hack啥原理
by bamboo1030 @ 2023-06-23 09:19:35
@[MichaelWong](/user/765446) 好像是那玩意儿day=945超级大
by bamboo1030 @ 2023-06-23 09:19:55
@[bamboo123](/user/369181) 是的，我输出了一下，一般的都是飞快，但是在固定的几个时间点会被卡（$day=124,226,338 \dots$），不知道是怎么回事……
by MichaelWong @ 2023-06-23 09:21:22