社区讨论
求助 WA9,10,long double求调
P7113[NOIP2020] 排水系统参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @m1kk68sl
- 此快照首次捕获于
- 2024/09/27 18:06 去年
- 此快照最后确认于
- 2025/11/04 18:41 4 个月前
使用过int_128类型,也是挂9,10
//蒟蒻变量名不好勿喷
CPP#include <bits/stdc++.h>
using namespace std;
long double waterup[100007];//分母
long double waterdown[100007];//分子
int fa[100007];//节点入度数
int last[100007];//最终排水口
int cnt;
int n,m;
vector<int>ed[100007];//图
inline long double gcd(long double a,long double b)
{
while(fmod(a,b)!=0&&fmod(b,a)!=0)
{
if(a<b)swap(a,b);
a=fmod(a,b);
}
if(a>b)return b;
else return a;
}
void pos(int i,long double a,long double b){//分数加法
long double gcdd1 = gcd(a,b);
a/=gcdd1;
b/=gcdd1;
waterup[i] = waterup[i]*b+waterdown[i]*a;
waterdown[i] *= b;
long double gcdd = gcd(waterup[i],waterdown[i]);
waterup[i]/=gcdd;
waterdown[i]/=gcdd;
return;
}
signed main(){
// freopen("P7113_9.in","r",stdin);
cin >> n >> m;
for(int i = 1;i<=100007;i++){
waterdown[i] = 1;
}//预处理,使分母不为 1
int k,d;
for(int i = 1;i<=n;i++){
cin >> k;
if(k == 0){//最终排水口
cnt++;
last[cnt] = i;
}
for(int j = 1;j<=k;j++){
cin >> d;
fa[d]++;
ed[i].push_back(d);
}
}
queue <int> q;
for(int i = 1;i<=n;i++){
if(fa[i] == 0){
q.push(i);
waterup[i] = 1;
}
}//预处理进水口
while(!q.empty()){
int init = q.front();
q.pop();
for(int i = 0;i<ed[init].size();i++){//拓扑排序
pos(ed[init][i],waterup[init],(waterdown[init]*ed[init].size()));
fa[ed[init][i]]--;
if(fa[ed[init][i]] == 0)q.push(ed[init][i]);//没有入度就入队列
}
}
for(int i = 1;i<=cnt;i++){
long double gcdd = gcd(waterup[last[i]],waterdown[last[i]]);//约分
long double a = waterup[last[i]]/gcdd;
long double b = waterdown[last[i]]/gcdd;
int64_t ia=a/1e15,ib=b/1e15;
if(ia)printf("%lld%015lld " ,ia,int64_t(a-ia*1e15));
else printf("%lld " ,int64_t(a));
if(ib)printf("%lld%015lld\n",ib,int64_t(b-ib*1e15));
else printf("%lld\n" ,int64_t(b));
}
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...