自动搬运

查看原文

来自洛谷，原作者为

	Ar_cher AFO.||永远的签名：铁肩担道义，妙手著文章。

搬运于2025-08-24 22:40:37，当前版本为作者最后更新于2022-11-15 17:46:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

A. 题意分析

对最后一组样例数据进行分析：

先画个草图，蓝色为节点的度。

先拿节点 $1$ 节点 $2$ 举例，节点 $1$ 的度为 $3$，节点 $2$ 的度为 $2$。

节点一和二之间是联通的，那么就把这条路径固定下来。然后看这两个节点所连的其他节点有哪些，实际上只需要知道有多少个即可，很显然就是节点的度数减一个。

这里节点 $2$ 剩下的相连节点只有 $3$，而 $1$ 剩下的相连节点有 $4$ 和 $3$，写出来路径：

$4\to1\to2\to3$

$3\to1\to2\to3$

由于双向的，所以又有 $4\to1\to2\to3$ 和 $3\to1\to2\to3$

同样，节点 $2$ 和节点 $3$ 的度均为 $2$，固定 $2\to3$ 路径，只有 $1\to2\to3\to1$ 和反过来的 $1\to3\to2\to1$

同理，节点 $3$ 和节点 $1$ 有 $4$ 种转发情况。

由于节点 $4$ 的度为 $1$，它只有与节点 $1$ 联通的这一种，题目要求需要转发两次，所以 $1\to4$ 不能作为中间路径。

B.完善程序

#include<bits/stdc++.h>
#define MAXN 10010
#define MAXM 100010
using namespace std;
int d[MAXN],u[MAXM],v[MAXM];
int main(){
	int n,i,m;
	long long ans=0;
	cin>>n>>m;
	memset(d,0,sizeof(d));
	for(i=0;i<m;i++){
		scanf("%d%d",&u[i],&v[i]);
		d[u[i]]++;
		d[v[i]]++;
	}
	for(i=0;i<m;i++){
		if(d[u[i]]>1&&d[v[i]]>1)
		ans+=(d[u[i]]-1)*(d[v[i]]-1)*2;
	}
	cout<<ans;
	return 0;
}

C.感谢

ice_fish01

wuningyu68

至高无上的管理员