社区讨论

萌新刚学OI求助大佬

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

讨论操作

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

当前回复
6 条
当前快照
1 份
快照标识符
@mi865t98
此快照首次捕获于
2025/11/21 09:16
4 个月前
此快照最后确认于
2025/11/21 09:16
4 个月前
查看原帖
求大佬帮忙改错
(60分,WA:Case1,6,9,10)
CPP
#include<bits/stdc++.h>
#define Inf 0x7fffffff
using namespace std;
queue<int> Q;
int a,b,x,n,m,k,Now,Last,Day,Start,End,Cnt,Used,Ans;
int Cycle[10010],Can[10010],Head[10010],Cur[10010],Dep[10010],To[200010],Next[200010],Val[200010],Stop[110][110];
template<typename T>
int Read(T &x){
    x=0;
    int f=1;
    char c=getchar();
    while(c!='-'&&!isdigit(c)){
        c=getchar();
    }
    while(!isdigit(c)){
        if(c=='-'){
            f=-f;
        }
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    x*=f;
    if(c=='\n'){
        return 1;
    }
    else{
        return 0;
    }
}
void Write(long long x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        Write(x/10);
    }
    putchar(x%10+'0');
}
inline void Add(int a,int b,int x){
    To[++Cnt]=b;
    Next[Cnt]=Head[a];
    Head[a]=Cnt;
    Val[Cnt]=x;
    To[++Cnt]=a;
    Next[Cnt]=Head[b];
    Head[b]=Cnt;
    Val[Cnt]=0;
}
bool Bfs(){
    memset(Dep,-1,sizeof(Dep));
    Dep[Start]=0;
    Q.push(Start);
    while(!Q.empty()){
        x=Q.front();
        Q.pop();
        for(int i=Head[x];i;i=Next[i]){
            if(Val[i]&&Dep[To[i]]==-1){
                Dep[To[i]]=Dep[x]+1;
                Q.push(To[i]);
            }
        }
    }
    return Dep[End]!=-1;
}
int Dfs(int x,int f){
    int w=0,Used=0;
    if(x==End){
        return f;
    }
    for(int i=Cur[x];i;i=Next[i]){
        if(Dep[To[i]]==Dep[x]+1){
            w=f-Used;
            w=Dfs(To[i],min(Val[i],w));
            Val[i]-=w;
            if(Val[i]){
                Cur[x]=i;
            }
            Val[i^1]+=w;
            Used+=w;
            if(Used==f){
                return f;
            }
        }
    }
    if(!Used){
        Dep[x]=-1;
    }
    return Used;
}
void Dinic(){
    while(Bfs()){
        for(int i=1;i<=10005;i++){
            Cur[i]=Head[i];
        }
        Ans+=Dfs(Start,Inf);
    }
}
int main(){
    Ans=0;
    Cnt=1;
    Read(n);
	Read(m);
	Read(k);
	Start=10001;
	End=10002;
	for(int i=1;i<=m;i++){
		Read(Can[i]);
		Read(Cycle[i]);
		for(int j=1;j<=Cycle[i];j++){
			Read(Stop[i][j]);
			if(Stop[i][j]<=0){
				Stop[i][j]+=(n+2);
			}
		}
	}
	Add(Start,n+2,Inf);
	Add(n+1,End,Inf);
	Day=0;
	while(Day<=500){
		Day++;
		Add(Start,(Day+1)*(n+2),Inf);
		Add(Day*(n+2)+n+1,End,Inf);
		for(int i=1;i<=n+2;i++){
			Add((Day-1)*(n+2)+i,Day*(n+2)+i,Inf);
		}
		for(int i=1;i<=m;i++){
			Now=Day%Cycle[i];
			if(Now==0){
				Now=Cycle[i];
			}
			Last=Now-1;
			if(Last<=0){
				Last+=Cycle[i];
			}
			Add(Stop[i][Last]+(Day-1)*(n+2),Stop[i][Now]+Day*(n+2),Can[i]);
		}
		Dinic();
		if(Ans>=k){
			break;
		}
	}
	if(Ans>=k){
		Write(Day-1);
	}
	else{
		Write(0);
	}
    return 0; 
}


 

回复

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

正在加载回复...