Pseudoforest
Time Limit:5000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit
Status
Description
In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. The maximal pseudoforests of G are the pseudoforest subgraphs of G that are not contained within any larger pseudoforest of G. A pesudoforest is larger than another if and only if the total value of the edges is greater than another one’s.
Input
The input consists of multiple test cases. The first line of each test case contains two integers, n( < n <= ), m( <= m <= ), which are the number of the vertexes and the number of the edges. The next m lines, each line consists of three integers, u, v, c, which means there is an edge with value c ( < c <= ) between u and v. You can assume that there are no loop and no multiple edges.
The last test case is followed by a line containing two zeros, which means the end of the input.
Output
Output the sum of the value of the edges of the maximum pesudoforest.
Sample Input
Sample Output
/*伪森林*/
这个题目类似于最小生成树，只不过是找最大的权值，但是不能直接写最大生成树，有个地方要注意，就是每个联通块只能有一个环，要加一个环的判定，以环为根节点。
如果两个生成树都有环就不能再相连。
对于同一个根的两个点，如果这个根已经成环，这两点不能在连接，如果没成环，就连上，标记成环。
看懂题目后挺简单，可是我还是wa了三次。。
代码：
#include"iostream"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"algorithm"
using namespace std;
const int MX=2e5+5;
struct nod {
int p; //根值
bool O; //是否联通成环
int sum;//总权值
} pe[MX];
struct node {
int s,e,q;//查询的两个点 s e 和 边的权值
} side[MX];
int find(int x) {
return pe[x].p==x?x:(pe[x].p=find(pe[x].p));
}
bool cmp(node a,node b) { //按照权值降序排序
return a.q>b.q;
}
int main() {
int n,m,maxx,flag;
while(~scanf("%d%d",&n,&m)) {
if(!n&&!m)break;
for(int i=0; i<=n; i++)pe[i].p=i,pe[i].O=0,pe[i].sum=0; //清空标记，清空环，清空总权值
for(int i=0; i<m; i++) {
scanf("%d%d%d",&side[i].s,&side[i].e,&side[i].q); //读入每一个点
}
sort(side,side+m,cmp);
maxx=0;
for(int i=0; i<m; i++) {
int rt1=find(side[i].s),rt2=find(side[i].e);
bool OK1=pe[rt1].O,OK2=pe[rt2].O;
if(rt1==rt2) {
if(OK1&&OK2)continue;//如果这个联通图内部已经构成环了，则不再连接这两点
pe[rt1].O=1;
pe[rt1].sum+=side[i].q;//找到两个根相同的节点，连起来就构成了最大环
}
if(rt1!=rt2) {
if(OK1&&OK2)continue; //如果两个联通图各自都已经有环了，则不再连接
if(!OK1&&OK2) {
pe[rt2].sum+=side[i].q+pe[rt1].sum; //以已经成环的根为根
pe[rt1].sum=0; //将未成环的根的总和清空
pe[rt1].p=rt2; //将未成环的根的根变为环
} else {
pe[rt1].sum+=side[i].q+pe[rt2].sum;
pe[rt2].sum=0;
pe[rt2].p=rt1;
}
}
}
for(int i=0; i<n; i++) {
maxx+=pe[i].sum;
}
printf("%d\n",maxx);
}
return 0;
}