WA了好多次,都找不出什么错误,最后队友看了disscuss才知道,原来连接两个顶点的边不止一条,应该取最小的,但是从题意中没有读出来,被虐了,悲剧呀!!!~~~~
题目大体意思是求n个环的并,每个点只能在一个环里,找到可以遍历所有顶点的边的最小值,显然每个点只能关联其他两个顶点,并且入度和初度都为1,所以应该是完全匹配,完全匹配图就是n个环的并,所以求的是完美匹配中的最小权问题,用km解决即可~
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; const int inf=10000000; const int N=205; int g[N][N]; //邻接矩阵 int lx[N],ly[N]; //顶点标号 bool sx[N],sy[N];//是否已经搜索过,S为寻找从i出发的增广轨时访问的x中的点的集合,T为访问的y中的点的集合。 int link[N]; int n; bool path(int k) //从x[k]寻找增广路 { int i; sx[k]=true; for(i=0; i<n; i++) { if(!sy[i]&&(lx[k]+ly[i]==g[k][i]))//相等子图 { sy[i]=1; if(link[i]==-1||path(link[i])) { link[i]=k; return true; } } } return false; } int BestMatch() //求解最小权匹配 { int i,j,k,d,sum; memset(ly,0,sizeof(ly));//初始化y的顶点标号 for(i=0; i<n; i++) { lx[i]=-1;//x中顶点i的编号为与i关联的Y中边的最大权重 for(j=0; j<n; j++) if(lx[i]<g[i][j]) lx[i]=g[i][j];//初始化x的顶点标号 } memset(link,-1,sizeof(link)); for(k=0; k<n; k++) { while(1) { memset(sx,0,sizeof(sx)); memset(sy,0,sizeof(sy)); if(path(k)) //匹配成功 break; d=inf; for(i=0; i<n; i++) { if(sx[i]) //x在交错树中 { for(j=0; j<n; j++) { if(!sy[j])//y不在交错树中,扩大子图 d=min(d,lx[i]+ly[j]-g[i][j]); } } }//若匹配不成功,则修改顶点标号,找到d的值 for(i=0; i<n; i++) { if(sx[i]) lx[i]-=d;//修改x顶点标号 if(sy[i]) ly[i]+=d;//修改y顶点标号 } } } sum=0; for(i=0; i<n; i++) sum+=g[link[i]][i]; sum*=-1; return sum; } int main() { int t; cin>>t; while(t--) { int m,ans,i,j; cin>>n>>m; for(i=0; i<n; i++) for(j=0; j<n; j++) g[i][j]=-inf;//即将边的权值取反 while(m--) { int u,v,w; cin>>u>>v>>w; if(g[--u][--v]<-w)//WA的地方,注意呀!!! g[u][v]=-w; } ans=BestMatch(); printf("%d\n",ans); } return 0; }