RE 0pts 求助
查看原帖
RE 0pts 求助
231600
zhangboju楼主2021/4/20 21:22

第一个数据点即为样例,在本地和洛谷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);
}
2021/4/20 21:22
加载中...