不断删去度数为1的点,最后求有奇数个点的联通块的权值之和。
存边的时候,要头尾都存这个边。用dfs或者队列删点,再用并查集或者dfs确定联通块,然后统计联通块的点数,最后累加。
我自己写的超时,然后参考了网上的题解。真郁闷。
#include<cstdio>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const int N = 1e4 + 10;
ll v[N];
ll s[N];
int n,m,e[N],f[N],cn[N];
vector<int> d[N];
int find(int a)
{
return f[a]==a?a:find(f[a]);
}
void unite(int a,int b)
{
a=find(a),b=find(b);
if(a!=b) f[a]=b;
}
void add(int a,int b)
{
e[a]++;
e[b]++;
d[a].push_back(b);
d[b].push_back(a);
unite(a,b);
}
void del()
{
queue<int>q;
for(int i=1; i<=n; i++) if(e[i]==1) q.push(i);
while(!q.empty())
{
int r=q.front();
q.pop();
for(int j=0; j<d[r].size(); j++)
{
int w=d[r][j];
e[w]--;
if(e[w]==1)q.push(w);
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
{
scanf("%lld",&v[i]);
e[i]=s[i]=cn[i]=0;
f[i]=i;
d[i].clear();
}
for(int i=1; i<=m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
del();
for(int i=1; i<=n; i++)
{
if(e[i]>1)
{
int a=find(i);
s[a]+=v[i];
cn[a]++;
}
}
ll ans=0;
for(int i=1; i<=n; i++)
{
if (f[i]==i && cn[i]&1)
{
ans+=s[i];
}
}
printf("%lld\n",ans);
}
return 0;
}
#include<cstdio>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
const int N = 1e4 + 10;
ll v[N];
int n,m,e[N],vis[N];
ll ct,sum;
vector<int> d[N];
void add(int a,int b)
{
e[a]++;
e[b]++;
d[a].push_back(b);
d[b].push_back(a);
}
void dfs(int a)
{
vis[a]=1;
sum+=v[a];
ct++;
for(int i=0; i<d[a].size(); i++)
{
int w=d[a][i];
if(!vis[w]) dfs(w);
}
}
void del()
{
queue<int>q;
for(int i=1; i<=n; i++)
{
if(e[i]==1) q.push(i);
if(e[i]==0) vis[i]=1; // 别忘了度为0的点
}
while(!q.empty())
{
int r=q.front();
vis[r]=1;
q.pop();
for(int j=0; j<d[r].size(); j++)
{
int w=d[r][j];
e[w]--;
if(e[w]==1)q.push(w);
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
{
scanf("%lld",&v[i]);
e[i]=vis[i]=0;
d[i].clear();
}
for(int i=1; i<=m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
del();
ll ans=0;
for(int i=1; i<=n; i++)
{
sum=ct=0;
if(!vis[i]) dfs(i);
if(ct&1)ans+=sum;
}
printf("%lld\n",ans);
}
return 0;
}