提交记录

RE 的第一个点数据如下：

input:
3 4 3
1 3 0 3 2
1 2 1 3
1 2 1 -1
1 2 -1 2
output:
9

然而无论是本地还是洛谷 IDE 都没有任何问题。

数组已经开得够大了，应该也没有出现数组下标负数等情况。

所以这是为什么？？？

附我的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 26;
int n,m,k,tot,s=0,t=1;
int tmp[20010000];
struct egde{
	int nxt,to,cap;
}e[20010000];
int cnt=1,head[N];
int h[N],r[N];
vector <int> v[N];
inline void add(int u,int v,int c){
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
	e[cnt].cap=c;
	tmp[cnt]=c;
}
int dis[10001000],work[10010000],ans;
queue <int> q;
bool bfs(int s,int t){
	q.push(s);
	memset(dis,0,sizeof(dis));
	dis[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].to;
			if(dis[v] || e[i].cap<=0) continue;
			dis[v]=dis[u]+1;
			q.push(v);
		}
	}
	return dis[t]>0;
}
int dfs(int u,int flow,int by,int t){
	if(u==t) return flow;
	for(int &i=work[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(dis[v]!=dis[u]+1 || e[i].cap<=0 || (i ^ 1)==by) continue;
		int res=dfs(v,min(flow,e[i].cap),i,t);
		if(!res) continue;
		e[i].cap-=res;
		e[(i ^ 1)].cap+=res;
		return res;
	}
	return 0;
}
int dinic(int s,int t){
	int ans=0;
	while(bfs(s,t)){
		for(int i=0;i<=tot;i++) work[i]=head[i];
		while(true){
			int flow=dfs(s,1e18,0,t);
			if(!flow) break;
			ans+=flow;
		}
	}
	for(int i=1;i<=cnt;i++) e[i].cap=tmp[i];
	return ans;
}
int fa[N];
int find(int x){
	if(fa[x]==x) return x;
	else return fa[x] = find(fa[x]);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=n+2;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		v[i].push_back(0);
		cin>>h[i]>>r[i];
		int u=-1,x=-1;
		for(int j=1;j<=r[i];j++){
			if(u!=-1) x=find(u);
			cin>>u;
			u+=2;
			v[i].push_back(u);
			if(x>=0) fa[x]=fa[find(u)];
		}
	}
	if(find(1)!=find(2)){
		cout<<0;
		return 0;
	}
	tot=1;
	while(++ans){
		tot+=n+1;
		add(s,2+(ans-1)*(n+1),1e18);
		add(2+(ans-1)*(n+1),s,0);
		if(ans>1){
			for(int i=2+(ans-1)*(n+1);i<=2+n+(ans-1)*(n+1);i++){
				add(i-n-1,i,1e18);
				add(i,i-n-1,0);
			}
			for(int i=1;i<=m;i++){
				int pos=v[i][(ans-1)%r[i]+1],lst=v[i][(ans-2)%r[i]+1];
				if(pos!=t) pos=(ans-1)*(n+1)+pos;
				if(lst!=t) lst=(ans-2)*(n+1)+lst;
				add(lst,pos,h[i]);
				add(pos,lst,0);
			}
		}
		int flow=dinic(s,t);
		if(flow>=k){
			cout<<ans-1;
			return 0;
		}
	}
	return 0;
}