社区讨论
我寻思这题就离谱
P2765魔术球问题参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6zivps
- 此快照首次捕获于
- 2025/11/20 13:22 4 个月前
- 此快照最后确认于
- 2025/11/20 13:22 4 个月前
CPP
#include <bits/stdc++.h>
using namespace std;
int m,n,k,t=10000,s,d[100010],head[100010];
struct p{
int w,v,next;
}st[1000010];
int add(int a,int b,int c){
st[++k].v=b;
st[k].w=c;
st[k].next=head[a];
head[a]=k;
}
int bfs(){
memset(d,0,sizeof(d));
queue<int> q;
q.push(0);
d[0]=1;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=st[i].next){
int v=st[i].v;
if(st[i].w>0&&d[v]==0){
d[v]=d[u]+1;
q.push(v);
}
}
}
//printf("%d\n",d[t]);
if(d[t])return 1;
else return 0;
}
int dfs(int u,int dis){
if(u==t){
//printf("%d\n",dis);
return dis;}
for(int i=head[u];i;i=st[i].next){
int v=st[i].v;
if(d[v]==d[u]+1&&st[i].w>0){
int di=dfs(v,min(dis,st[i].w));
if(di>0){
st[i].w-=di;
st[i^1].w+=di;
return di;
}
}
}
return 0;
}
int ans,vis[100010],num,to[100010];
int main()
{
cin>>n;
t=10000;
for(;1;){
ans++;num++;
for(int i=1;i<num;i++)
if(sqrt(i+num)==(int)sqrt((i+num))){
add(i,num+5000,1),add(num+5000,i,0);
// printf("%d %d\n",i,num);
}
add(0,num,1);
add(num,0,0);
add(num+5000,t,1);
add(t,num+5000,0);
while(bfs())ans-=dfs(0,1000000000);
if(ans>n)break;
}
printf("%d\n",num-1);
for(int i=1;i<num;i++){
int j=head[i];
while(j){
if(!st[j].w){
// printf("%d %d\n",i,st[j].v-5000);
to[i]=st[j].v-5000;break;}
j=st[j].next;
}
}
for(int i=1;i<num;i++)
{
if(vis[i])continue;int t=i;
while(t>0){
vis[t]=1;
printf("%d ",t);
t=to[t];
}
printf("\n");
}
return 0;
}```
这样交在洛谷re完,codevs上wa完,自己看输出都是对的,神tmadd函数改成void类型就能A,太离谱辣!!!!
回复
共 4 条回复,欢迎继续交流。
正在加载回复...