[PA2014]Kuglarz【BZOJ 3714】【差分约束 + 最小生成树】_带约束的最小生成树问题

BZOJ 3714 题目链接

  这题有个坑点，头文件里不能放“#include <unordered_map>”，会CE的，不知道为什么，反正我CE了好久，好懵逼！

  然后讲一下思路吧，首先是看到数据范围N只有最大2000，很容易会想时间O(N^2)也是可以的，然后我们从一个点的时候来看，一个点只需要一个点就可以了，确定两个点的时候，也是需要两条关系，三个点的时候就比较特殊了，我们也是要三条信息，但是假如三条信息都比较的特殊，都是1、2之间的关系，是显然不行的，所以要避免这个关系，再想想，关系必须要取N个，也就是意味着我们只需要挑其中的互不冲突的N条关系即可？

  怎么维护互不冲突，N条关系，我们是不是可以看成N条边，而且在固定N条边，是不是可以看成我们现在对N+1个点去做一个最小生成树（MST）即可，为什么成立呢？手玩，或者差分约束的思想跑一下，就可以理解到了。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
//#include <unordered_map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define max3(a, b, c) max(a, max(b, c))
#define max6(a, b, c, d, f, g) max(max3(a, b, c), max3(d, f, g))
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 2e3 + 7;
int N, T;
ll mp[maxN][maxN], lowercost[maxN];
bool vis[maxN];
ll Prime()
{
    ll ans = 0;
    for(int i=1; i<=T; i++) lowercost[i] = mp[1][i];
    for(int i=1; i<=T; i++) vis[i] = false;
    lowercost[1] = 0;
    ll minn = INF;
    int id = 0;
    vis[1] = true;
    for(int line=1; line<=N; line++)
    {
        minn = INF;
        for(int i=1; i<=T; i++)
        {
            if(!vis[i] && lowercost[i] < minn)
            {
                minn = lowercost[i];
                id = i;
            }
        }
        vis[id] = true;
        ans += minn;
        for(int i=1; i<=T; i++) lowercost[i] = min(lowercost[i], mp[id][i]);
    }
    return ans;
}
int main()
{
    scanf("%d", &N);    T = N + 1;
    for(int i=1; i<=N; i++)
    {
        for(int j=i; j<=N; j++)
        {
            scanf("%lld", &mp[i][j + 1]);
            mp[j + 1][i] = mp[i][j + 1];
        }
    }
    printf("%lld\n", Prime());
    return 0;
}
/*
5
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5
*/