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