【CZY选讲·一道图论神题】

题目描述

LYK有一张无向图G={V,E}，这张无向图有n个点m条边组成。并且这是一张带权图，只有点权。 LYK想把这个图删干净，它的方法是这样的。每次选择一个点，将它删掉，但删这个点是需要代价的。假设与这个点相连的还没被删掉的点是u1,u2,…,uk。LYK 将会增加a[u1],a[u2],…,a[uk]的疲劳值。 它想将所有点都删掉，并且删完后自己的疲劳值之和最小。你能帮帮它吗？

数据范围：

数据保证任意两个点之间最多一条边相连，并且不存在自环。

1<=n,m,ai<=100000。

题解：
①贪心策略是从权值大的点开始删，统计答案就是了。

②证明：每一条边会被删除一次,那么尽可能先删掉这条边权值较大的那一端点.

③CZY官方证明：

把删点转化成删边，定义一条边的边权为一对点后删的点的点权，最后每条边都是要被删掉的。

对于每条边，肯定优先删除点权大的点。

正确性证明：将无向图中的边按点权大的点向点权小的点连有向边，最后一定是一张DAG图。

#include<cstdio>

#include<algorithm>

#define LL long long

using namespace std;

const int N=100005;

int n,m,u,v,a[100005];LL ans;

int main(){

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    while(m--)

	{

        scanf("%d%d",&u,&v);

        ans+=min(a[u],a[v]);

    }

    printf("%lld\n",ans);

    return 0;

}//czy020202

你有没有感到,也许永远只能视而不见。

你有没有扔过一枚硬币,选择正反面。————汪峰《硬币》

巴特西

【CZY选讲·一道图论神题】

最新文章

热门文章