題意：

有n個(gè)池塘、m個(gè)管道，每個(gè)池塘有權(quán)值，m個(gè)管道用來(lái)連接池塘（無(wú)向邊），我們要把度小于2的池塘刪除，統(tǒng)計(jì)每個(gè)包含池塘數(shù)是奇數(shù)的連通分量的權(quán)值并輸出。

思路：

拓?fù)渑判蛑?#xff0c;刪點(diǎn)，然后dfs一遍就好了。因?yàn)橛胕nt沒(méi)用long long WA了一次。

代碼；

#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std;const long long maxn = 10005; long long du[maxn]; long long val[maxn]; queue<int> q;struct E {long long to, next; }e[100005]; long long tot; long long head[maxn]; void init() {memset(head, 0, sizeof(head));tot =1; } void add(long long u, long long v) {e[tot].to = v;e[tot].next = head[u]; head[u] = tot++; }long long vis[maxn]; long long ans = 0;long long cnt = 0; void dfs(long long u, long long &num, long long &sum) {for(long long i = head[u]; i; i = e[i].next) {long long v = e[i].to;if(!vis[v]) {vis[v] = 1;num++;sum += val[v];dfs(v, num, sum);}} }int main() {long long t;long long n, m;scanf("%I64d",&t);while(t--) {init();scanf("%I64d %I64d",&n, &m);for(long long i = 1; i <= n; i++) {scanf("%I64d",&val[i]);}memset(du, 0, sizeof(du));for(long long i = 1; i <= m; i++) {long long u, v;scanf("%I64d %I64d",&u, &v);du[u]++; du[v]++;add(u, v);add(v, u);}while(!q.empty()) q.pop();memset(vis, 0, sizeof(vis));for(long long i = 1; i <= n; i++) {if(du[i] <= 1){vis[i] = 1;q.push(i);}}while(!q.empty()) {long long u = q.front(); q.pop();for(long long i = head[u]; i; i = e[i].next) {long long v = e[i].to;if(!vis[v]) {du[v] --;if(du[v] <= 1) {vis[v] = 1;q.push(v);}}}}ans = 0;for(long long i = 1; i <= n; i++) {if(!vis[i]) {vis[i] = 1;long long num = 1, sum = val[i];dfs(i, num, sum);if(num % 2 == 1) {ans += sum;}}}printf("%I64d\n", ans);} }

總結(jié)

以上是生活随笔為你收集整理的hdu5438(2015长春网络赛B题)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。