HDU 5438 Ponds （搜索）

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5438

題面：

Ponds Time Limit: 1500/1000 MS (Java/Others)????Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1308????Accepted Submission(s): 439


Problem Description Betty owns a lot of ponds, some of them are connected with other ponds by pipes, and there will not be more than one pipe between two ponds. Each pond has a value v.

Now Betty wants to remove some ponds because she does not have enough money. But each time when she removes a pond, she can only remove the ponds which are connected with less than two ponds, or the pond will explode.

Note that Betty should keep removing ponds until no more ponds can be removed. After that, please help her calculate the sum of the value for each connected component consisting of a odd number of ponds ?
Input The first line of input will contain a number T(1≤T≤30) which is the number of test cases.

For each test case, the first line contains two number separated by a blank. One is the number p(1≤p≤104) which represents the number of ponds she owns, and the other is the number m(1≤m≤105) which represents the number of pipes.

The next line contains p numbers v1,...,vp, where vi(1≤vi≤108) indicating the value of pond i.

Each of the last m lines contain two numbers a and b, which indicates that pond a and pond b are connected by a pipe. ?
Output For each test case, output the sum of the value of all connected components consisting of odd number of ponds after removing all the ponds connected with less than two pipes. ?
Sample Input

1 7 7 1 2 3 4 5 6 7 1 4 1 5 4 5 2 3 2 6 3 6 2 7 ?
Sample Output

21 ?
Source 2015 ACM/ICPC Asia Regional Changchun Online

題目大意：

??? 給定一些池塘，池塘之間連有一些管道。要求將不連管道或者只連一根管道的池塘消去，問最后剩下連在一起且池塘個數(shù)為奇數(shù)的池塘權(quán)值總和。

解題：

??? 比賽的時候，以為是什么奇環(huán)，后來發(fā)現(xiàn)又不是，思路整體跑偏了。正確的解法是，通過bfs或者dfs不斷消去度數(shù)為1的點，消完之后，再用dfs找聯(lián)通塊即可。以下提供兩種解法，實際上沒什么實質(zhì)差別，復(fù)雜度都為O(m),因為每條邊最多遍歷一次。

解法一：

??? dfs+dfs

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL long long
int pond[10010];
//鄰接表
struct edge
{
	int next,to,vis;//下一條邊序號，到哪個點，邊是否被斷開
}store[200010];
int head[10010],cnt,degree[10010],num;//head存儲每個點連向的第一條邊的存儲下標(biāo)，-1代表該點當(dāng)前已經(jīng)沒有邊了
//cnt加邊的下標(biāo)，degree度數(shù)，num聯(lián)通塊中的塊數(shù)
bool vist[10010];//數(shù)聯(lián)通塊時的標(biāo)記
LL sum;//存儲聯(lián)通塊的總和
//加邊
void addedge(int a,int b)
{
   store[cnt].to=b;
   store[cnt].next=head[a];
   store[cnt].vis=false;
   head[a]=cnt++;
}
//消去池塘
void dfs(int x)
{
   int tmp;
   tmp=head[x];
   degree[x]=0;
   //還未到最后一條邊
   while(tmp!=-1)
   {
	   if(degree[store[tmp].to])
	   {
		  //tmp和tmp^1代表相鄰兩條邊
          store[tmp].vis=store[tmp^1].vis=true;
          degree[store[tmp].to]--;
		  //如果度數(shù)為1，繼續(xù)搜索
		  if(degree[store[tmp].to]==1)
		  	  dfs(store[tmp].to);
	   }
	   //移向下一條邊
	   tmp=store[tmp].next;
   }
   return;
}
void dfs2(int x)
{
   int tmp,v;
   vist[x]=1;
   tmp=head[x];
   while(tmp!=-1)
   {
	 //如果這條邊還沒斷開
     if(!store[tmp].vis)
     {
         v=store[tmp].to;
         if(!vist[v]&°ree[v])
         {
             num++;
             sum+=pond[v];
             dfs2(v);
         }
     }
     tmp=store[tmp].next;
   }
}
int main()
{
    int t,p,m,u,v,tmp,cas=1;
	LL ans;
	scanf("%d",&t);
	while(t--)
	{
      scanf("%d%d",&p,&m);
	  memset(head,-1,sizeof(head));
	  memset(degree,0,sizeof(degree));
	  memset(vist,0,sizeof(vist));
	  cnt=ans=0;
      for(int i=1;i<=p;i++)
		  scanf("%d",&pond[i]);
	  for(int i=1;i<=m;i++)
	  {
		  scanf("%d%d",&u,&v);
		  addedge(u,v);
		  addedge(v,u);
          degree[u]++;
		  degree[v]++;
	  }
	  //搜索度數(shù)為1的池塘
	  for(int i=1;i<=p;i++)
		  if(degree[i]==1)
			  dfs(i);
	  //統(tǒng)計結(jié)果
	 for(int i=1;i<=p;i++)
      {
          if(degree[i]&&!vist[i])
          {
              sum=pond[i];
              num=1;
              dfs2(i);
              if(num%2)
                  ans+=sum;
          }
      }
      printf("%lldn",ans);
	}
	return 0;
}

解法二：

??? bfs+dfs

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int pond[10010];
struct edge
{
    int next,to;
}store[200010];
int head[10010],cnt,degree[10010];
bool vist[10010],cut_off[200010];
long long sum;
int num;
queue  qe;
inline void addedge(int a,int b)
{
   store[cnt].to=b;
   store[cnt].next=head[a];
   head[a]=cnt++;
}
void bfs()
{
    int tmp,cur,v;
    while(!qe.empty())
    {
      cur=qe.front();
      qe.pop();
      tmp=head[cur];
      while(~tmp)
      {
          v=store[tmp].to;
          if(degree[v])
          {
              cut_off[tmp]=cut_off[tmp^1]=1;
              degree[v]--;
              if(degree[v]==1)
              {
                  qe.push(v);
                  degree[v]=0;
              }
          }
          tmp=store[tmp].next;
      }
    }
}
void dfs(int x)
{
   int tmp,v;
   vist[x]=1;
   tmp=head[x];
   while(tmp!=-1)
   {
     if(!cut_off[tmp])
     {
         v=store[tmp].to;
         if(!vist[v])
         {
             num++;
             sum+=pond[v];
             dfs(v);
         }
     }
     tmp=store[tmp].next;
   }
}
int main()
{
    int t,p,m,u,v;
    long long  ans;
    scanf("%d",&t);
    while(t--)
    {
      scanf("%d%d",&p,&m);
      memset(head,-1,sizeof(head));
      memset(degree,0,sizeof(degree));
      memset(vist,0,sizeof(vist));
      memset(cut_off,0,sizeof(cut_off));
      cnt=0,ans=0;
      for(int i=1;i<=p;i++)
          scanf("%d",&pond[i]);
      for(int i=1;i<=m;i++)
      {
          scanf("%d%d",&u,&v);
          addedge(u,v);
          addedge(v,u);
          degree[u]++;
          degree[v]++;
      }
      for(int i=1;i<=p;i++)
          if(degree[i]==1)
               qe.push(i),degree[i]=0;
      bfs();
      for(int i=1;i<=p;i++)
      {
          if(degree[i]&&!vist[i])
          {
              sum=pond[i];
              num=1;
              dfs(i);
              if(num%2)
                  ans+=sum;
          }
      }
      printf("%lldn",ans);
    }
    return 0;
}