题解 P3037 【[USACO11DEC]简化的农场Simplifying the Farm】

ShuYuMo · 2019-08-04 09:37:38 · 题解

思路

如果没有边权相同的边，那么其实时不存在多种最小生成树的方案的。

题目中同一边权的个数不超过三个

按照Kruskal的建树流程进行模拟。

边权排完序后，边权相同的会聚到一起，然后在从小到大枚举的时候分类讨论即可。

流程

首先找到边权相同到的几条边。

这是我们需要在这些边中选出有用边。

所谓有用边就是加入其中一条边，不会产生环。因为之前已经加入的边是不能再反悔的，所以如果当前等待加入的边与之前的边存在矛盾的话，当前边一定是无用的。 如下图，下图的橙色边就是无用边：

然后我们考虑哪些情况会使最小生成树方案增加：

• 如过当前权值有两条边相同： 就有这两种情况：

  • 对于第一种情况，这两条边只能同时加入其中任意一条，这样就有两种建树方案。 对于第二种情况，这两条边没有选择余地，必须都加入。

• 如过当前权值有三条边相同： 以下三种情况能产生多种建树方案：

  • 这三种情况分别产生3（选其中一条不加入），2（选重复的两条中的一条），3（选三条中的任意一条）种生成树方案。

代码

使用set帮助区分三条边权相同时，第一种情况和第二种情况。

/*!
 * FileName: luogu-3037.cpp
 * This Problem is on luogu. The ID of the problem is 3037. 
 * Copyright(c) 2019 Shu_Yu_Mo
 * MIT Licensed
 * Luogu: https://www.luogu.org/space/show?uid=44615
 * Github: https://github.com/oldsuold/
 * Gitee: https://gitee.com/Shu_Yu_Mo/
 * These words were created by an amazing tool on 2019-08-03 22:47:58 written by Shu_Yu_Mo.
 */
#include<cstdio>
#include<cstring>
#include<iostream>
#include<set>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
const int _M = 1e5 + 100;
const int _N = 4e4 + 100;
const int MOD = 1000000007;
inline int read()
{
    char c = getchar(); int sign = 1; int x = 0;
    while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } 
    while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
    return x * sign;
}
struct edges{
    int u;
    int v;
    int w;
    bool operator < (const edges & A) const {
        return w < A.w;
    }
}E[_M];
int n, m;
//Kruskal 所用的并查集   Start
int f[_N];
int find(int x){ return f[x] == x ? x : f[x] = find(f[x]); }
void initForSet()
{
    for(register int i = 1;i <= n;i++)
        f[i] = i;
}
void marge(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y) return;
    f[x] = y;
}
bool ask(int x, int y)
{
    return find(x) == find(y);
}
//Kruskal 所用的并查集   End
int nxtIt(int now)//往下找最后一个边权相同的位置
{
    for(register int i = now;i <= m;i++)
        if(E[now].w != E[i].w)
            return i - 1;
    return m;
}
set <pair<int , int >  >  S;//
int main()
{
    n = read(), m = read();
    for(register int i = 1;i <= m;i++)
    {
        E[i].u = read();
        E[i].v = read();
        E[i].w = read(); 
    }
    initForSet();
    sort(E + 1, E + 1 + m);
    int ans1 = 0;
    int ans2 = 1;
    int nxt;
    for(register int i = 1;i <= m;)
    {
        S.clear();
        nxt = nxtIt(i);
        int totEdge = 0;
        for(register int j = i;j <= nxt;j++)
            if(!ask(E[j].u, E[j].v))
            {
                totEdge ++;
                int k1 = min(find(E[j].u), find(E[j].v));
                int k2 = max(find(E[j].u), find(E[j].v));
                S.insert(make_pair(k1, k2));
            }
        int totAdd = 0;
        for(register int j = i;j <= nxt;j++)
        {
            if(!ask(E[j].u, E[j].v))
            {
                marge(E[j].u, E[j].v);
                totAdd ++;
                ans1 = (ans1 + E[j].w) % MOD;
            }
        }
        if(totAdd == 1)
            ans2 = ans2 * 1LL * totEdge % MOD;//分别是两条边权相同时的第一种情况    和    三条边权相同时的第三种情况。
        if(totAdd == 2 && totEdge == 3)
        {
            if(S.size() == 3) ans2 = ans2 * 3LL % MOD;//三条边权相同时的第一种情况
            if(S.size() == 2) ans2 = ans2 * 2LL % MOD; //三条边权相同时的第二种情况
        }
        i = nxt + 1;
    }
    printf("%d %d\n", ans1 % MOD, ans2 % MOD);
    return 0;
}