Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 哪位牛人帮忙看看 floyed+KM为什么WA啊…………

Posted by mopishv1 at 2008-08-24 16:24:09 on Problem 2404 and last updated at 2008-08-24 17:09:49
```#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;
}```

Followed by: