hdu5438 Ponds[DFS,STL vector二维数组]

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目地址
题干
代码和解释
参考

题目地址

hdu5438

题干

代码和解释

解答本题时参考了一篇代码较短的博客，比较有意思，使用了STL vector二维数组。

可以结合下面的示例代码理解：

#include<iostream> #include<vector> using namespace std; int main() { vector<int> n[100]; int i; for(i=0;i<100;i++){ n[i].clear(); } n[5].push_back(1); n[5].push_back(3); printf("%d\n",n[5].size());//为2 printf("%d\n",n[5][0]);//为1 printf("%d\n",n[5][1]);//为3 //printf("%d\n",n[5]);//编译不通过 return 0; }

可以理解为100行一维数组，每行长度不定，vector相当于变长数组。所以之前一维数组时对 n （vector<int> n）的操作在这里都对 n[i] (vector<int> n[100];int i;)应用。

本题的dfs跟网上的dfs基本模板差别有点大，不太易于作为dfs学习的开始，这里不详细解释。

这里是c++代码。

#include<iostream> #include<vector> #include<cstring> #include<cstdio> using namespace std; int v[10010],f[10010],l[10010];//v存储每个池塘的值，f存储其是否被遍历过，l存储每个池塘连接管子数 vector<int> x[10010];//x存储每个池塘与哪个池塘相连的具体情况 int tmp;//tmp是已经遍历的节点个数 long long sum1,sum2; void dfs(int t); int main() { int T,p,m,a,b;//T为样例组数，p为池塘数，m为连接组合数，a、b为每组连接中两个池塘的位置（编号） int i,j; int flag; scanf("%d",&T); while(T--){ scanf("%d%d",&p,&m); sum1=0; memset(v,0,sizeof(v)); memset(f,0,sizeof(f)); memset(l,0,sizeof(l));//初始化 for(i=0;i<10010;i++){ x[i].clear();//初始化 } for(i=1;i<=p;i++){//从1开始到p结束，不然会错，因为a和b存储位置是从1开始的 scanf("%d",&v[i]); } for(i=0;i<m;i++){ scanf("%d%d",&a,&b); x[a].push_back(b);//a与b相连 x[b].push_back(a);//b与a相连 l[a]++;//与a相连的池塘（管子）数加1 l[b]++;//与b相连的池塘（管子）数加1 } flag=1; while(flag==1){ flag=0;//如果所有剩下的池塘连接管子数都大于等于2，则flag就会保持为0 for(i=1;i<=p;i++){//i从1开始到p if(l[i]==0||l[i]==1){ //连接管子数小于2 flag=1;//只要这样的池塘还存在，就让flag为1，重新执行循环 f[i]=1;//表示已经遍历过 for(j=0;j<x[i].size();j++){//x[i].size表示位置为i的这个池塘连接的管子数 l[x[i][j]]--;//让所有与位置为i的池塘相连的池塘的连接管子数减1，即删除了位置为i的池塘与其他池塘的连接关系 } l[i]=-1;//表示连接管子数小于2 } } } //这样处理完后就只剩下连接管子数大于等于2的池塘，接下来用dfs判断每个连接组合是否包含奇数个池塘 for(i=1;i<=p;i++){//i从1开始到p if(f[i]==0){ //说明是还没有遍历过的 sum2=0; tmp=0; dfs(i);//经过这个操作，tmp变成这个组合中池塘的数量，sum2变成这个组合中所有池塘值的和，并且这个组合中所有池塘都被遍历过了 if(tmp%2==1){//如果包含奇数个池塘 sum1+=sum2; } } } printf("%lld\n",sum1); } return 0; } void dfs(int t){ int i; tmp++; f[t]=1;//表示已经遍历过，这样就不会对同一个组合中的每个池塘多次计算了 sum2+=v[t];//加上这个池塘的值 for(i=0;i<x[t].size();i++){ if(f[x[t][i]]==0){//对于与这个池塘相连的所有未被遍历过的池塘 dfs(x[t][i]); } } return; }