社区讨论

求助dalao,WA date2,怎么改?

P2754[CTSC1999] 家园 / 星际转移问题参与者 4已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi6mmthu
此快照首次捕获于
2025/11/20 07:21
4 个月前
此快照最后确认于
2025/11/20 07:21
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
#define INF 2100000000
struct node {
    int to;
    int flow;
    int next;
}e[1000000];
int head[10000];
int cur[10000];
int d[10000];
int f[10000];
int h[30];
int p[30];
int r[30][20];
int thetime[30];
int fa[10000];
int s,t,tot=1,n,m,k,TIME;
int read() {
    int ans=0,flag=1;
    char ch=getchar();
    while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
    if(ch=='-') flag=-1,ch=getchar();
    while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans*flag;
}
void addedge(int u,int v,int w) {
    e[++tot].to=v;
    e[tot].flow=w;
    e[tot].next=head[u];
    head[u]=tot;
    e[++tot].to=u;
    e[tot].flow=0;
    e[tot].next=head[v];
    head[v]=tot;
    return ;
}
int find(int x) {
    fa[x]==x ? fa[x] : fa[x]=find(fa[x]);
    return fa[x];
}
void merge(int x,int y) {
    int fx=find(x),fy=find(y);
    if(fx!=fy) fa[fx]=fy;
    return ;
}
int dfs(int now,int flow) {
    if(now==t) return flow;
    int use=0;
    for(int i=cur[now];i;i=e[i].next) {
        cur[now]=i;
        if(d[e[i].to]+1==d[now] && e[i].flow>0) {
            int temp=dfs(e[i].to,min(flow-use,e[i].flow));
            use+=temp;
            e[i].flow-=temp;
            e[i^1].flow+=temp;
            if(use==flow) return flow;
        }
    }
    cur[now]=head[now];
    if(!(--f[d[now]]))
        d[s]=(n+1)*(TIME+1)+2;//gap
    ++f[++d[now]];
    return use;
}
int main() {
    freopen("in","r",stdin);
    n=read(),m=read(),k=read();
    for(int i=1;i<=n+2;i++) fa[i]=i;
    for(int i=1;i<=m;i++) {
        h[i]=read();
        p[i]=read();
        for(int j=0;j<p[i];j++) {
            r[i][j]=read();
            if(r[i][j]==0) r[i][j]=n+1;
            if(r[i][j]==-1) r[i][j]=n+2;
            if(j!=0) merge(r[i][j-1],r[i][j]);
        }
    }
    if(find(n+1)!=find(n+2)) {
        printf("0");
        return 0;
    }
    TIME=0;
    while(++TIME) {
        memset(e,0,sizeof(e));
        memset(d,0,sizeof(d));
        memset(f,0,sizeof(f));
        memset(cur,0,sizeof(cur));
        memset(head,0,sizeof(head));
        memset(thetime,0,sizeof(thetime));
        s=(n+1)*(TIME+1)+1;
        t=(n+1)*(TIME+1)+2;
        addedge(s,n+1,INF);
        for(int i=1;i<=TIME;i++) {
            for(int j=1;j<=n+1;j++)
                addedge(j+(i-1)*(n+1),j+i*(n+1),INF);
            for(int j=1;j<=m;j++) {
                int now=thetime[j]++;
                thetime[j]%=p[j];
                if(r[j][thetime[j]]==n+2)
                    addedge(r[j][now]+(i-1)*(n+1),t,h[j]);
                else
                    addedge(r[j][now]+(i-1)*(n+1),r[j][thetime[j]]+i*(n+1),h[j]);
            }
        }
        f[0]=(n+1)*(TIME+1)+2;
        int ans=0;
        while(d[s]<(n+1)*(TIME+1)+2) {
            ans+=dfs(s,1<<30);
        }
        if(ans>=k) {
            printf("%d",TIME);
            break;
        }
    }
    return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...