題目描述
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
你有沒有感到,也許永遠隻能視而不見。
你有沒有扔過一枚硬币,選擇正反面。————汪峰《硬币》
轉載于:https://www.cnblogs.com/Damitu/p/7654390.html