P8605 题解

· · 题解

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

至高无上的管理员