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