5 条题解

  • 2
    @ 2025-10-15 9:24:19

    解答

    这题用分数？不可能的！！！

    因为我整天被分数创，所以我想尽办法把分数规避掉。

    因为过程上最多经过 1212 个节点（算上开头和结尾），我们另一个把初始流量从 11 改成 lcm⁡(2,3,4,5)12=6012\operatorname{lcm}(2,3,4,5) ^ {12} = 60 ^ {12} ，这样全程都不会出现分数。

    然后进行拓扑排序就行了。

    最后答案就是 该点流量6012 \frac{该点流量}{60^{12}} 。

    注意：请使用 __int128 ，否则保龄。

    code

    #include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
struct node
{
	__int128 p;
};
__int128 qpow(__int128 a,__int128 b)
{
	__int128 c=1;
	for(int i=1;i<=b;i++) c*=a;
	return c;
}
void out(__int128 x)
{
	if(x==0) cout<<0;
	stack<int> st;
	while(st.size()) st.pop();
	while(x)
	{
		st.push(int(x%10));
		x/=10;
	}
	while(st.size()) cout<<st.top(),st.pop();
}
int n,m;
queue<int> q;
vector<int> ed;
__int128 w[N];
int d[N];
vector<int> e[N];
__int128 tmp=qpow(60,12);
__int128 gcd(__int128 a,__int128 b)
{
	if(b==0) return a;
	else return gcd(b,a%b);
}
int rudu[N];
int main()
{

	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>d[i];
		for(int j=1;j<=d[i];j++)
		{
			int v;
			cin>>v;
			e[i].push_back(v);rudu[v]++;
		}
		if(d[i]==0) ed.push_back(i);
	}
	for(int i=1;i<=n;i++)
	{
		if(rudu[i]==0)
		{
			q.push(i);
			w[i]=tmp;
		}
	}
	while(q.size())
	{
		int u=q.front();
		q.pop();
		__int128 dd=d[u];
		for(auto v:e[u])
		{
			rudu[v]--;
			w[v]+=w[u]/dd;
			if(rudu[v]==0) q.push(v);
		}
	}
	for(auto i:ed)
	{
		__int128 q=tmp,p=w[i];
		__int128 res=gcd(q,p);
		q/=res;p/=res;
		out(p);cout<<' ';out(q);cout<<'\n';
	}
	return 0;
}
    • 1
      @ 2025-10-13 14:01:31

      給定的圖是一個DAG，所以顯然使用拓撲排序

      每次對於一個入度為 00 的點 uu，假設該點會流入 xx 大小的水，那給所有 uu 可以到達的點 vv，向其中加入 xoudu\frac{x}{oud_u} 的水

      然後就是考慮分數的問題，顯然有：

      $$\frac{x}{y} \times \frac{1}{z} = \frac{\frac{x}{\gcd(x,z)}}{y\times \frac{z}{\gcd(x,z)}} $$$$\frac{x}{y} + \frac{a}{b} = \frac{x\times b + a\times y}{y\times b} $$

      注意不要使用long long要改成__int128

      #include<iostream>
#include<cstdio>
#include<queue>
#define int __int128
using namespace std;
bool Test_MLE_start;
const int N=1e5+10;
int _=1,n,m,tot=0,head[N],ind[N],oud[N],fm[N],fz[N];
struct edge{int v,nxt;}a[N<<1];
queue<int> q;
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
void writes(int x){
	if(x>9) writes(x/10);
	putchar(x%10+'0');
}
inline void files(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
void add(int u,int v){
	a[++tot].v=v,ind[v]++,oud[u]++;
	a[tot].nxt=head[u];
	head[u]=tot;
}
int gcd(int n,int m){return m?gcd(m,n%m):n;}
void solve(int &fz1,int &fm1,int fz2,int fm2){
	if(!fz1&&!fm1) fz1=fz2,fm1=fm2;
	else{
		int GCD=gcd(fm1*fm2,fz1*fm2+fz2*fm1);
		fz1=(fz1*fm2+fz2*fm1)/GCD,fm1=fm1*fm2/GCD;
	}
}
bool Test_MLE_end;
signed main(){// LL ¼«¶ËÊý¾Ý 
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads();
		for(int i=1;i<=n;i++){
			int k;k=reads();
			while(k--){
				int v;v=reads();
				add(i,v);
			}
		}
		for(int i=1;i<=n;i++){
			if(!ind[i]) fz[i]=fm[i]=1,q.push(i);
		}
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=head[u];i;i=a[i].nxt){
				int v=a[i].v,GCD=gcd(fz[u],oud[u]);
				int adfz=fz[u]/GCD,adfm=oud[u]/GCD*fm[u];
				solve(fz[v],fm[v],adfz,adfm);
				if(!(--ind[v])) q.push(v);
			}
		}
		for(int i=1;i<=n;i++){
			if(!oud[i]) writes(fz[i]),printf(" "),writes(fm[i]),printf("\n");
		}
	}
	return 0;
}
      • 1
        @ 2025-10-13 14:00:25

        给定的图是一个DAG，所以显然使用拓扑排序

        每次对于一个入度为 00 的点 uu ，假设该点会流入 xx 大小的水，那给所有 uu 可以到达的点 vv ，向其中加入 xoudu\frac{x}{oud_u} 的水

        然后就是考虑分数的问题，显然有：

        $$\frac{x}{y} \times \frac{1}{z} = \frac{\frac{x}{\gcd(x,z)}}{y\times \frac{z}{\gcd(x,z)}} $$$$\frac{x}{y} + \frac{a}{b} = \frac{x\times b + a\times y}{y\times b} $$

        注意不要使用long long要改成__int128

        #include<iostream>
#include<cstdio>
#include<queue>
#define int __int128
using namespace std;
bool Test_MLE_start;
const int N=1e5+10;
int _=1,n,m,tot=0,head[N],ind[N],oud[N],fm[N],fz[N];
struct edge{int v,nxt;}a[N<<1];
queue<int> q;
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
void writes(int x){
	if(x>9) writes(x/10);
	putchar(x%10+'0');
}
inline void files(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
void add(int u,int v){
	a[++tot].v=v,ind[v]++,oud[u]++;
	a[tot].nxt=head[u];
	head[u]=tot;
}
int gcd(int n,int m){return m?gcd(m,n%m):n;}
void solve(int &fz1,int &fm1,int fz2,int fm2){
	if(!fz1&&!fm1) fz1=fz2,fm1=fm2;
	else{
		int GCD=gcd(fm1*fm2,fz1*fm2+fz2*fm1);
		fz1=(fz1*fm2+fz2*fm1)/GCD,fm1=fm1*fm2/GCD;
	}
}
bool Test_MLE_end;
signed main(){// LL ¼«¶ËÊý¾Ý 
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads();
		for(int i=1;i<=n;i++){
			int k;k=reads();
			while(k--){
				int v;v=reads();
				add(i,v);
			}
		}
		for(int i=1;i<=n;i++){
			if(!ind[i]) fz[i]=fm[i]=1,q.push(i);
		}
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=head[u];i;i=a[i].nxt){
				int v=a[i].v,GCD=gcd(fz[u],oud[u]);
				int adfz=fz[u]/GCD,adfm=oud[u]/GCD*fm[u];
				solve(fz[v],fm[v],adfz,adfm);
				if(!(--ind[v])) q.push(v);
			}
		}
		for(int i=1;i<=n;i++){
			if(!oud[i]) writes(fz[i]),printf(" "),writes(fm[i]),printf("\n");
		}
	}
	return 0;
}
        • -1
          @ 2025-10-13 13:50:17

          按照题意模拟即可。

          通分的时候可能会爆 long long，所以改成 long double 或 __int128 。

          #include<bits/stdc++.h>
#define R(x) x=read()
#define int __int128
using namespace std;
inline int read() {
	int x=0,y=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+(c^'0');
		c=getchar();
	}
	return x*y;
}
void write(int x){
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const int N=200005;
int gcd(int x,int y) {
	if(y==0)return x;
	return gcd(y,x%y);
}
int n,m;
int a[N],b[N];
int d[N];
int ans[N],tot;
vector<int>G[N];
queue<int>q;
int ind[N];
signed main() {
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
	R(n),R(m);
	for(int i=1,x; i<=n; ++i) {
		R(d[i]);
		for(int j=1;j<=d[i];++j) {
			R(x);
			G[i].push_back(x);
			++ind[x];
		}
		if(!d[i])ans[++tot]=i;
	}
	for(int i=1; i<=n; ++i) {
		b[i]=1;
		if(!ind[i]) {
			a[i]=1;
			q.push(i);
		}
	}
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(auto v:G[u]){
			int av=a[v],bv=b[v];
			a[v]=av*b[u]*d[u]+bv*a[u];
			b[v]=bv*b[u]*d[u];
			int g=gcd(a[v],b[v]);
			a[v]/=g,b[v]/=g;
			if(!(--ind[v]))q.push(v);
		}
	}
	for(int i=1;i<=tot;++i){
		write(a[ans[i]]),putchar(' '),write(b[ans[i]]),putchar('\n');
	}
	return 0;
}
          • -2
            @ 2025-10-13 14:03:31

            The given graph is a DAG, so it is obvious to use topological sorting

            For each point uu with a degree of 00 , assuming that the point will flow with water of xx size, add water of xoudi\frac {x} {oud_i} to all points vv that uu can reach

            Then there is the issue of considering scores, which obviously includes:

            $$\frac{x}{y} \times \frac{1}{z} = \frac{\frac{x}{\gcd(x,z)}}{y\times \frac{z}{\gcd(x,z)}} $$$$\frac{x}{y} + \frac{a}{b} = \frac{x\times b + a\times y}{y\times b} $$

            Be careful not to use long long instead of __int128

            #include<iostream>
#include<cstdio>
#include<queue>
#define int __int128
using namespace std;
bool Test_MLE_start;
const int N=1e5+10;
int _=1,n,m,tot=0,head[N],ind[N],oud[N],fm[N],fz[N];
struct edge{int v,nxt;}a[N<<1];
queue<int> q;
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
void writes(int x){
	if(x>9) writes(x/10);
	putchar(x%10+'0');
}
inline void files(){
	freopen("water.in","r",stdin);
	freopen("water.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
void add(int u,int v){
	a[++tot].v=v,ind[v]++,oud[u]++;
	a[tot].nxt=head[u];
	head[u]=tot;
}
int gcd(int n,int m){return m?gcd(m,n%m):n;}
void solve(int &fz1,int &fm1,int fz2,int fm2){
	if(!fz1&&!fm1) fz1=fz2,fm1=fm2;
	else{
		int GCD=gcd(fm1*fm2,fz1*fm2+fz2*fm1);
		fz1=(fz1*fm2+fz2*fm1)/GCD,fm1=fm1*fm2/GCD;
	}
}
bool Test_MLE_end;
signed main(){// LL ¼«¶ËÊý¾Ý 
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads();
		for(int i=1;i<=n;i++){
			int k;k=reads();
			while(k--){
				int v;v=reads();
				add(i,v);
			}
		}
		for(int i=1;i<=n;i++){
			if(!ind[i]) fz[i]=fm[i]=1,q.push(i);
		}
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=head[u];i;i=a[i].nxt){
				int v=a[i].v,GCD=gcd(fz[u],oud[u]);
				int adfz=fz[u]/GCD,adfm=oud[u]/GCD*fm[u];
				solve(fz[v],fm[v],adfz,adfm);
				if(!(--ind[v])) q.push(v);
			}
		}
		for(int i=1;i<=n;i++){
			if(!oud[i]) writes(fz[i]),printf(" "),writes(fm[i]),printf("\n");
		}
	}
	return 0;
}
            • 1

            [NOIP2020] 排水系统

            信息

            ID
            466
            时间
            1000ms
            内存
            256MiB
            难度
            9
            标签
            (无)
            递交数
            8
            已通过
            6
            上传者
            1. 关于
            2. 联系我们
            3. 隐私
            4. 服务条款
            5. 版权申诉
            6. Language
            7. 兼容模式
            8. 主题
            3. Worker 0, 59ms
            4. Powered by Hydro v4.18.3 Community