整晚都耗在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 >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 lx[i]) lx[i]=map[i][l]; } for(z=0;z 再给出标准模板： #include好了，今晚到这，明天再来改下，洗洗睡了#include #include #include #include