HDU 5438 Ponds dfs模拟

2015 ACM/ICPC Asia Regional Changchun Online

题意：n个池塘，删掉度数小于2的池塘，输出池塘数为奇数的连通块的池塘容量之和.

思路：两个dfs模拟就行了

 #include <iostream>

 #include <cstdio>

 #include <fstream>

 #include <algorithm>

 #include <cmath>

 #include <deque>

 #include <vector>

 #include <queue>

 #include <string>

 #include <cstring>

 #include <map>

 #include <stack>

 #include <set>

 #define LL long long

 #define eps 1e-8

 #define INF 0x3f3f3f3f

 #define MAXN 10005

 using namespace std;

 vector<int> G[MAXN];

 int  father[MAXN], cnt[MAXN], du[MAXN];

 LL v[MAXN];

 bool rm[MAXN], vis[MAXN];

 struct Node{

     int pos, du;

     Node(int pos = , int du = ) :pos(pos), du(du){};

 };

 bool compare(Node x, Node y){

     return x.du < y.du;

 }

 int find(int x){

     if (father[x] == x) return x;

     father[x] = find(father[x]);

     return father[x];

 }

 void dfs(int x, int p){

     vis[x] = true;

     father[x] = p;

     for (int i = ; i < G[x].size(); i++){

         int y = G[x][i];

         if (rm[y] || vis[y]) continue;

         dfs(y, p);

     }

 }

 void dfs_rm(int x){

     rm[x] = true;

     for (int i = ; i < G[x].size(); i++){

         du[G[x][i]]--;

         if (du[G[x][i]] <  && !rm[G[x][i]]) dfs_rm(G[x][i]);

     }

 }

 Node node[MAXN];

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int T;

     int m, n;

     scanf("%d", &T);

     while (T--){

         scanf("%d%d", &n, &m);

         memset(du, , sizeof(du));

         for (int i = ; i <= n; i++){

             scanf("%I64d", &v[i]);

             G[i].clear();

         }

         int x, y;

         for (int i = ; i <= m; i++){

             scanf("%d%d", &x, &y);

             du[x]++;

             du[y]++;

             G[x].push_back(y);

             G[y].push_back(x);

         }

         memset(rm, , sizeof(rm));

         //sort(node + 1, node + n + 1, compare);

         for (int i = ; i <= n; i++){

             //int x = node[i].pos;

             if (du[i] >  || rm[i]) continue;

             dfs_rm(i);

         }

         int p = ;

         memset(father, , sizeof(father));

         memset(vis, , sizeof(vis));

         for (int i = ; i <= n; i++){

             if (rm[i] || vis[i]) continue;

             dfs(i, p);

             p++;

         }

         memset(cnt, , sizeof(cnt));

         for (int i = ; i <= n; i++){

             if (rm[i]) continue;

             //int x = find(i);

             cnt[father[i]]++;

         }

         LL ans = ;

         for (int i = ; i <= n; i++){

             if (cnt[father[i]] & ){

                 ans += v[i];

             }

         }

         printf("%I64d\n", ans);

     }

 }