第一个数据点即为样例,在本地和洛谷IDE均可以正常运行,提交RE,求助
数组大小应该不是问题,毕竟小数据 RE
#include<bits/stdc++.h>
using namespace std;
const int N=150005,M=N*3,inf=0x7f7f7f7f;
#define pa(x) (x%2==0?x-1:x+1)
struct node{
int v,nxt,c;
}e[M*2];
int head[N],cnt=1;
void add(int u,int v,int c)
{
e[cnt].v=v;
e[cnt].c=c;
e[cnt].nxt=head[u];
head[u]=cnt++;
}
int n,m,k;
struct ship{
int h,r;
int s[25];
}a[25];
int fa[N];
int findx(int x)
{
if(fa[x]!=x) return fa[x]=findx(fa[x]);
return fa[x];
}
int merge(int x,int y)
{
x=findx(x),y=findx(y);
if(x!=y) fa[y]=x;
}
int s,t;
int get(int x,int day)
{
return day*(n+2)+x;
}
int d[N],cur[N];
queue<int>q;
bool bfs()
{
while(!q.empty()) q.pop();
memset(d,-1,sizeof d);
q.push(s),d[s]=0,cur[s]=head[s];
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(d[v]==-1&&e[i].c)
{
d[v]=d[u]+1;
cur[v]=head[v];
if(v==t) return true;
q.push(v);
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==t) return limit;
int flow=0;
for(int i=cur[u];i&&flow<limit;i=e[i].nxt)
{
cur[u]=i;
int v=e[i].v;
if(d[v]==d[u]+1&&e[i].c)
{
int t=find(v,min(e[i].c,limit-flow));
if(!t) d[v]=-1;
e[i].c-=t,e[pa(i)].c+=t,flow+=t;
}
}
return flow;
}
long long dinic()
{
long long r=0,flow;
while(bfs()) while(flow=find(s,inf)) r+=flow;
return r;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
s=N-1,t=N-2;
for(int i=0;i<=n+1;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a[i].h,&a[i].r);
for(int j=1;j<=a[i].r;j++)
{
scanf("%d",&a[i].s[j]);
if(a[i].s[j]==-1) a[i].s[j]=n+1;
if(j>1) merge(a[i].s[j-1],a[i].s[j]);
}
}
if(findx(0)!=findx(n+1))
{
puts("0");
return 0;
}
add(s,0,k);add(0,s,0);
add(n+1,t,inf);add(t,n+1,0);
int day=1,res=0;
while(1)
{
add(get(n+1,day),t,inf),add(t,get(n+1,day),0);
for(int i=0;i<=n+1;i++)
add(get(i,day-1),get(i,day),inf),add(get(i,day),get(i,day-1),0);
for(int i=1;i<=m;i++)
{
int r=a[i].r;
int x=a[i].s[(day-1)%r+1],b=a[i].s[day%r+1];
add(get(x,day-1),get(b,day),a[i].h),add(get(b,day),get(x,day-1),0);
}
res+=dinic();
if(res>=k) break;
day++;
}
printf("%d",day);
}