签到水题啊。。。
这题完全跟图论没有关系。
显然如果确定了哪些点会被选之后顺序已经不重要了。于是我们给点按权值排序贪心从大向小选。
我们要求的显然就是∑i(a[i]−(n−i))" role="presentation" style="position: relative;">∑i(a[i]−(n−i))∑i(a[i]−(n−i))
当这个贡献非正时停止枚举。
然后就没了。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 200005
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,m;
ll a[N],ans=0;
int main(){
freopen("eat.in","r",stdin);
freopen("eat.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=m;++i)int x=read(),y=read();
sort(a+1,a+n+1);
for(int i=n,cnt=0;i;--i,++cnt){
if(a[i]<=cnt)break;
ans+=a[i]-cnt;
}
cout<<ans;
return 0;
}