#include<iostream>
using namespace std;
const int INF=1000000000;
int map[21][21];
int d[21];
int n,m;
int edge[21][21],match[21];
int jd[21]={0},k=0;
bool xckd[121],yckd[21];
bool ma[21][21];
void floyed()//floyed求全源最短路径
{
	for(int i=0;i<n;i++)
	{
 		for(int j=0;j<n;j++)
 		{
       		if(map[j][i]!=-1)
       		{
         		for(int k=0;k<n;k++)
         		{
           			if(map[i][k]!=-1&&(map[j][k]==-1||map[j][k]>map[j][i]+map[i][k]))
           			{
           				map[j][k]=map[j][i]+map[i][k];
           				map[k][j]=map[j][i]+map[i][k];
           			}				
             	}
          	}
        }
  	}
}
void make()
{
    int i,j;    
	for(i=0;i<k;i++)
    {
    	for(j=0;j<k;j++)
    	{
    	    if(jd[i]!=jd[j])    
    			edge[i][j]=-map[jd[i]][jd[j]];
   			else
   				edge[i][j]=-INF;
  		}  		
    }
}

int max(int a,int b)
{
	return a>b?a:b;
}

int min(int a,int b)
{
	return a<b?a:b;
}

bool hungary(int p)//匈牙利算法求最大匹配 
{
    int i,j,l;
	for(i=0;i<k;i++)
	{
 		if(!yckd[i]&&ma[p][i])
 		{
   			yckd[i]=true;
   			if(match[i]==-1||hungary(match[i]))
   			{
          		match[i]=p;
          		return true;
           	}
           	if(match[i]!=-1) 
            	xckd[match[i]]=true;
     	}
  	}
  	return false;
}

void KM_Match()//KM算法求最大权值匹配 
{
    int i,j,l;
	int lx[21],ly[21];  
	for(i=0;i<k;i++) 
 	{ 
        lx[i]=-INF;  
        for(j=0;j<k;j++) 
        {
         	lx[i]=max(lx[i],edge[i][j]);
          	ly[j]=0; 
      	}   	
	}
	bool perfect=false;
	while(!perfect)
	{
   		for(i=0;i<k;i++) 
 		{ 
            for(j=0;j<k;j++) 
            {  
            	if(lx[i]+ly[j]==edge[i][j])
             		ma[i][j]=true; 
            	else 
             		ma[i][j]=false; 
    	 	} 
     	}
		int live=0;
		for(i=0;i<=k;i++)
			match[i]=-1;
		for(i=0;i<k;i++)
		{
		    for(j=0;j<=k;j++)
		    {
		        xckd[j]=false;
		        yckd[j]=false;
      		}   	
         	if(hungary(i))
         		live++;
     		else 
       		{ 
            	xckd[i]=true; 
            	break; 
         	}
       	}
       	if(live==k)
       		perfect=true;
   		else
   		{
     		int ex=INF;
     		for(i=0;i<k;i++)
     		{
           		for(j=0;xckd[i]&&j<k;j++)
           		{
             		if(!yckd[j])
               			ex=min(ex, lx[i]+ly[j]-edge[i][j]);
              	}
            }
            for(i=0;i<k;i++) 
            { 
            	if(xckd[i])
             		lx[i]-=ex; 
         	}
         	for(i=0;i<k;i++)
         	{
          		if(yckd[i])
            		ly[i]+=ex; 
           	}
      	}
  	}
}
int main()
{
    int i,j;
    while(scanf("%d",&n)!=EOF&&n!=0)
    {
    	scanf("%d",&m);
    	for(i=0;i<n+1;i++)
    	{
    	    d[i]=0;
    		for(j=0;j<n+1;j++)
    			map[i][j]=-1;
   		} 			
   		int sum=0;
		for(j=0;j<m;j++)
		{
      		int s,e,l;
      		scanf("%d%d%d",&s,&e,&l);
      		s--;
      		e--;
      		d[s]++;
      		d[e]++;
      		sum+=l;
      		map[s][e]=l;
      		map[e][s]=l;
       	}
       	floyed();
       	k=0;
       	for(i=0;i<n;i++)
       	{
        	if(d[i]%2==1)
        	{
         		jd[k]=i;
         		k++;
          	}
        }
        if(k!=0)
        {
        	make();
        	KM_Match();
        	int cost=0;
        	for(i=0;i<k;i++) 
   			{
       		    if(match[i]!=-1)
      				cost+=edge[match[i]][i]; 
   			} 
        	printf("%d\n",sum-cost/2);
    	}
     	else if(k==0)
      		printf("%d\n",sum); 
    }
	return 0;
}

• Re:哪位牛人帮忙看看 floyed+KM为什么WA啊………… (76) liruoke 2010-10-24 21:32:53
  • 感谢这位大牛的数据,,,,,原来似乎不能用费用流或者KM来算,,, (448) yy17yy 2011-03-07 21:45:04
    • Re:感谢这位大牛的数据,,,,,原来似乎不能用费用流或者KM来算,,, (376) zcube 2012-07-27 09:32:58
      • Re:感谢这位大牛的数据,,,,,原来似乎不能用费用流或者KM来算,,, (2) zcube 2012-07-27 09:34:18