A simple Blog for wyx I've been down the bottle hoping.
4886: [Lydsy2017年5月月赛]叠塔游戏 dp
发表于: | 分类: Oi | 评论:0 | 阅读:68

首先他要求要用上所有的牌【划重点】

看错题的可以回去重新想去了

然后我们考虑他那个递增P用没有,其实就是让你确定一组互不相同的底,然后让高的和最大

考虑在边权直接连边

然后考虑$i\to j$表示以$i$为底$j$为高

然后这题大概就变得傻逼了一半,显然就是每个点保证一个出度,那么统计出度之后每个点的贡献就是$val_i\times (deg_i-1)$

然后考虑如果是一颗树的话可以把最大点拎出来当根,所以再判一下是不是树

判断是不是树可以用边数/度数判,这个就不用我说了吧

#include <map>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 5e5+5;
const int M = N << 1;
using namespace std;
typedef long long LL;
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-'0';ch = getchar();}
    return x*f;
}

map <int,int> id;
int val[N], deg[N], sum, mx;
bool vis[N];
LL ans;

int head[N];

struct graph {
    int next, to, val;
    graph () {}
    graph (int _next,int _to)
    :next(_next), to(_to){}
}edge[M];

inline void add(int x,int y) {
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y); head[x] = cnt; deg[x] ++;
    edge[++cnt] = graph(head[y], x); head[y] = cnt; deg[y] ++;
} 

inline void DFS(int x) {
    if(vis[x]) return;
    vis[x]  = 1;
    mx = max(mx, val[x]);
    ans += (LL)val[x] * (deg[x]-1);
    sum += deg[x] - 2;
    for(int i=head[x];i;i=edge[i].next) {
        if(!vis[edge[i].to])
            DFS(edge[i].to);
    }
}

int cnt;

int main() {
    int n = read();
    for(int i=1;i<=n;++i) {
        int x = read(), y = read();
        if(!id.count(x)) {
            id[x] = ++ cnt;
            val[cnt] = x;
        }
        if(!id.count(y)) {
            id[y] = ++ cnt;
            val[cnt] = y;
        }
        add(id[x], id[y]);
    }
    for(int i=1;i<=cnt;++i) {
        if(!vis[i]) {
            sum = 0;
            mx = 0;
            DFS(i);
            if(sum < 0) ans += mx;
        }
    }
    cout << ans << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP