首页 > 代码库 > HDU 3367 Pseudoforest

HDU 3367 Pseudoforest

2024-07-21 19:23:30   217人阅读

【原题】

http://acm.hdu.edu.cn/showproblem.php?pid=3367

【题意】

给出一张图，求最大生成树。要求每一个连通块上只能有一个环。

【分析】

对于Kruskal来说，最小/最大生成树只是改变一下排序顺序即可。这里需要另外注意添加的就是对环的判断了：

如果两个节点不在同一棵树内，且分别不成环，则可合并；

如果两个节点在同一棵树内，但是未成环，则加上这条边之后将成环；

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5  6 using namespace std; 7  8 typedef struct nod 9 {10     int x,y,c;11 } node;12 node a[100010];13 14 bool op(node a,node b)15 {16     return a.c>b.c;17 }18 19 int father[10010];20 bool flag[10010];21 22 void clean_father(int n)23 {24     for (int i=0;i<n;i++) father[i]=i;25 } 26 27 int getfather(int x)28 {29     if (father[x]!=x) father[x]=getfather(father[x]);30     return father[x];31 }32 33 void link(int x,int y)34 {35     father[getfather(x)]=getfather(y);36 } 37 38 int main()39 {40     int n,m;41     while (scanf("%d%d",&n,&m))42     {43         if (n==0&&m==0) break;44         45         for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);46         sort(&a[1],&a[m+1],op);47         48         clean_father(n);49         memset(flag,0,sizeof(flag));50         int ans=0;51         for (int i=1;i<=m;i++)52         if (getfather(a[i].x)!=getfather(a[i].y))53         {54             if (!(flag[getfather(a[i].x)]&&flag[getfather(a[i].y)]))55             {56                 57                 if (flag[getfather(a[i].x)]||flag[getfather(a[i].y)])58                 {59                     flag[getfather(a[i].x)]=true;60                     flag[getfather(a[i].y)]=true;61                 }62                 link(a[i].x,a[i].y);63                 ans+=a[i].c;64             }65         } else 66         if (!flag[getfather(a[i].x)])67         {68             ans+=a[i].c;69             flag[getfather(a[i].x)]=true;70         }71         72         printf("%d\n",ans);73     }74     75     return 0;76 }
View Code

 

HDU 3367 Pseudoforest


联系
我们