Submission #2139150

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<ll,ll> pint;

ll vl[100001];
bool used[100001];
vector<int> g[100001];
ll dfs(int v,int p){
    ll ret=vl[v];
    used[v]=true;
    rep(i,g[v].size()){
        if(g[v][i]==p){
            if(count(g[v].begin(),g[v].end(),p)>1){
                ret=0;
            }
        }
        else if(used[g[v][i]]){
            ret=0;
        }
        else ret=min(ret,dfs(g[v][i],v));
    }
    return ret;
}
int main(){
    int n,m,xi,yi;
    ll sum=0;
    cin>>n>>m;
    rep(i,n){
        cin>>vl[i];
        sum+=vl[i];
    }
    rep(i,n) used[i]=true;
    rep(i,m){
        cin>>xi>>yi;
        --xi,--yi;
        g[xi].pb(yi);
        g[yi].pb(xi);
        used[xi]=used[yi]=false;
    }
    rep(i,n) if(used[i]) sum-=vl[i];
    rep(i,n)if(!used[i]){
        sum-=dfs(i,-1);
    }
    cout<<sum<<endl;
    return 0;
}

Submission Info

Judge Result