CF107A Dorm Water Supply 题解

题目简述

给出一个 $n$ 个点，$m$ 条边的有向图，边带权。保证每个点的出度和入度最多为 $1$。

• 对于每一个入度为 $0$，出度为 $1$ 的点，我们在该点建一个水箱 。
• 对于每一个入度为 $1$，出度为 $0$ 的点，我们在该点建一个水龙头。

可以发现，每一个水箱对应一个唯一的水龙头，我们将每对对应的水龙头和水箱称为一个水器组。

请求出每一个水箱到他对应的水龙头的路径上的边权最小值。

题目分析

我们可以先找到每一个水箱，由于题目保证了每一个水箱对应一个唯一的水龙头，所以我们可以直接从水箱开始搜索，直到找到它所对应的水龙头，在搜索的过程中记录答案即可。

代码

#include<iostream>
using namespace std;
const int N=1010;
const int M=1e6;
int n,p,a,b,d,in[N],head[N],cnt,vis[N],out[N],ans1[N],ans2[N],ans3[N],cnt1;
struct edge
{
	int to,next,value;
}e[M];
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
	    if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
	    x=(x<<1)+(x<<3)+ch-48;
	    ch=getchar();
	}
	return x*f;
}
inline void write(int x)
{
    if(x<0)
	{
    	putchar('-');
		x=-x;
	}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
void addedge(int u,int v,int w)
{
	e[++cnt]={v,head[u],w};
	head[u]=cnt;
	in[v]++;
	out[u]++;
}
void dfs(int now,int root,int ans)
{
	if(vis[now]) return;
	vis[now]=1;
	if(!out[now])
	{
		ans1[++cnt1]=root;
		ans2[cnt1]=now;
		ans3[cnt1]=ans;
		return;
	}
	for(int i=head[now];i;i=e[i].next)
	{
		int nxt=e[i].to;
		int w=e[i].value;
		dfs(nxt,root,min(ans,w));
	}
}
int main()
{
	n=read();
	p=read();
	for(int i=1;i<=p;i++)
	{
		a=read();
		b=read();
		d=read();
		addedge(a,b,d);
	}
	for(int i=1;i<=n;i++)
	{
		if(!in[i]&&out[i]>0)//本题的一个坑点，水箱不能是一个独立的点
		{
			dfs(i,i,999999999);
		}
	}
	write(cnt1);
	printf("\n");
	for(int i=1;i<=cnt1;i++)
	{
		printf("%d %d %d\n",ans1[i],ans2[i],ans3[i]);
	}
	return 0;
}