整晚都耗在KM上了。。。。果然不完全理解代码模板用起来太吃力了，其中若使用取负值的时候在正常KM模板上会在中途出错，之前也没给出标准的KM模板
当然这题的字典树可以不要，而且我用的也很粗糙有很多东西还能优化，但是加深了对字典树的使用，所以说知道结构之后会非常灵活方便呀~~~
最后今天编辑一下，总结下KM算法要注意的地方，首先是边值n,m控制好，然后就是建图:
要注意的是：若图不能将图填满，则需将空白处赋值0。
若求的是最小边权，这个模板需要用一个大数减去权值来求得最小，而不能用负数。
若求的是最大边权之积，可以用取自然对数，求出结果再e^ans;
给出挫代码:
#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int N=211;
const int MAXN=1<<20;
int n,m,t,i,x,y,c,e,j;
char a[22],b[22];
int lx[N],ly[N],visx[N],visy[N],slack[N],match[N],opp[N],map[N][N];
struct Tree{
int num;
int count;
Tree *next[100];
Tree()
{
num=0;
count=0;
for(int i=0;i<100;i++)
{
next[i]=NULL;
}
}
}* root1,* root2;
int insert(Tree *p,char *s)
{
int i=0,tmp;
p->count++;
tmp=p->count;
while(s[i])
{
int x=s[i]-'A';
if(p->next[x]==NULL)
p->next[x]=new Tree();
p=p->next[x];
i++;
}
p->num=tmp;
return p->num;
}
int find(Tree *p,char *s)
{
int i=0,ans=0;
while(s[i])
{
int n=s[i]-'A';
if(p->next[n])
{
p=p->next[n];
ans=p->num;
i++;
}
else {return 0;}
}
return ans;
}
void build()
{
for(i=0;i<n;i++)
for(int l=0;l<m;l++)
map[i][l]=-MAXN;
root1=new Tree();
root2=new Tree();
for(i=0;i<e;i++)
{
cin>>a>>b;
x=find(root1,a);
y=find(root2,b);
if(x==0)
{
x=insert(root1,a);
}
if(y==0)
{
y=insert(root2,b);
}
cin>>c;
map[x-1][y-1]=-c;
}
/*for(int i=0;i<n;i++)
{
cout<<endl;
for(int j=0;j<m;j++)
cout<<map[i][j]<<" ";
}*/
}
int dfs(int k)
{
visx[k]=1;
for(int i=0;i<m;i++)
{
if(visy[i]) continue;
int t=lx[k]+ly[i]-map[k][i];
if(!t)
{
visy[i]=1;
if(match[i]==-1 || dfs(match[i]))
{
match[i]=k;
opp[k]=i;
return 1;
}
}
else if(t<slack[i]) slack[i]=t;
}
return 0;
}
int KM()
{
int z,i,l;
memset(ly,0,sizeof(ly));
for(i=0;i<n;i++)
{
lx[i]=map[i][0];
for(l=1;l<m;l++) if(map[i][l]>lx[i]) lx[i]=map[i][l];
}
for(z=0;z<n;z++)
{
for(i=0;i<m;i++) slack[i]=MAXN;
while(1)
{
memset(visx,0,sizeof(visx));
memset(visy,0,sizeof(visy));
if(dfs(z)) break;
int min=MAXN;
for(i=0;i<m;i++) if(!visy[i] && slack[i]<min) min=slack[i];
for(i=0;i<n;i++) if(visx[i]) lx[i]-=min;
for(i=0;i<m;i++)
{
if(visy[i]) ly[i]+=min;
else slack[i]-=min;
}
}
}
int ans=0;
for(i=0;i<n;i++) ans+=map[i][opp[i]];
return ans;
}
int main()
{
int i;
while(scanf("%d%d%d",&n,&m,&e)!=-1)
{
build();
memset(opp,-1,sizeof(opp));
memset(match,-1,sizeof(match));
cout<<-KM()<<endl;
}
return 0;
}
再给出标准模板：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define CLR(arr, what) memset(arr, what, sizeof(arr))
#define maxn 305
#define INF (1<<30)-1
int g[maxn][maxn];
int lx[maxn],ly[maxn];
int match[maxn];
bool visx[maxn],visy[maxn];
int slack[maxn];
char matrix[maxn][maxn];
int n,m,e;
void build()
{
map<string, int> l;
map<string, int> c;
char lv[25], cao[25];
int injury, num1, num2;
int result;
num1 = num2 = 1;
result = 0;
CLR(match, -1);
CLR(g, 0);
l.clear(); c.clear();
for(int i = 0; i < e; ++i)
{
scanf("%s%s%d", lv, cao, &injury);
if(!l[lv])
l[lv] = num1++;
if(!c[cao])
c[cao] = num2++;
g[l[lv]][c[cao]] = 9999 - injury;
}
/*for(i=0;i<n;i++)
{
cout<<endl;
for(int j=0;j<m;j++)
cout<<map[i][j]<<" ";
}*/
}
bool dfs(int cur){
visx[cur] = true;
for(int y=1;y<=m;y++){
if(visy[y]) continue;
int t=lx[cur]+ly[y]-g[cur][y];
if(t==0){
visy[y] = true;
if(match[y]==-1||dfs(match[y])){
match[y] = cur;
return true;
}
}
else if(slack[y]>t){
slack[y]=t;
}
}
return false;
}
int KM(){
memset(match,-1,sizeof(match));
memset(ly,0,sizeof(ly));
for(int i=1 ;i<=n;i++){
lx[i]=0;
for(int j=1;j<=m;j++)
if(g[i][j]>lx[i]) lx[i]=g[i][j];
}
for(int x=1;x<=n;x++){
for(int i=1;i<=m;i++) slack[i]=INF;
while(true){
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
if(dfs(x)) break;
int d=INF;
for(int i=1;i<=m;i++){
if(!visy[i]&&d>slack[i]) d=slack[i];
}
for(int i=1;i<=n;i++){
if(visx[i]) lx[i]-=d;
}
for(int i=1;i<=m;i++){
if(visy[i]) ly[i]+=d;
else slack[i]-=d;
}
}
}
int result = 0;
for(int i = 1; i <=m; i++)
if(match[i]!=-1)
result += g[match[i]][i];
return result;
}
int main(){
while(scanf("%d%d%d",&n,&m,&e)!=EOF,n){
build();
for(int i=1;i<=n;i++)
{
cout<<endl;
for(int j=1;j<=m;j++)
cout<<g[i][j]<<" ";
}
printf("%d\n",9999*n-KM());
}
return 0;
}
好了，今晚到这，明天再来改下，洗洗睡了