社区讨论

P7113 排水系统 0pts求解答orz

灌水区参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@loig5v0x
此快照首次捕获于
2023/11/03 18:02
2 年前
此快照最后确认于
2023/11/03 20:20
2 年前
查看原帖
rt 样例第一个过了
CPP
#include<bits/stdc++.h>
using namespace std;
int e[10000][10000];//范围不够(我知道,想问为什么WA) 
queue<int>qwq;
int n,m,d[10000],a[100001],g[100001];//g是入度,a,d,m,n是题目上的 
float w[100001];//当前管道的污水量 
bool s[10001];//判断是不是输出管道 
int xiao(float jj){  //小数转分数 
	for(int r=1;r<=100;r++){
		for(int j=1;j<=100;j++){
			if((((float)r/j-jj<=0.001&&(float)jj<=(float)r/j)||((float)jj-r/j<=0.001&&(float)jj>=(float)r/j))&&__gcd(r,j)==1){
				cout<<r<<" "<<j<<endl;
				return 0;
			}
		}
	}
}
void bfs(){ //经典广搜 
	int o=qwq.front();
	if(s[o]==1) return;
	if(qwq.empty()) return;
	if(g[o]==0){
		for(int i=1;i<=d[o];i++){
			qwq.push(e[o][i]);
			w[e[o][i]]=w[o]/d[o]+w[e[o][i]];
			g[e[o][i]]--;
		}
		qwq.pop();
		bfs();
	}else{
		g[o]--;
		qwq.pop();
		return;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>d[i];
		if(d[i]==0){
			s[i]=1;
		}
		if(i<=m){
			w[i]=1;//赋值 
			qwq.push(i);
		}else{
			w[i]=0;
		}
		for(int j=1;j<=d[i];j++){
			cin>>a[j];
			g[a[j]]=g[a[j]]+1;
			e[i][j]=a[j];
		}
	}
	bfs();
	for(int i=1;i<=n;i++){
		if(s[i]==1){
			xiao(w[i]);
		}
	}
	return 0;
}

回复

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

正在加载回复...