社区讨论

我寻思这题就离谱

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 条回复,欢迎继续交流。

正在加载回复...