社区讨论
萌新刚学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 条回复,欢迎继续交流。
正在加载回复...