二分图最大权匹配是KM算法，我可以想到可行顶标和相等子图

一般图的最大权匹配还是带花树算法

不带权的匹配默认权是1

1 #include 
     
        2 #define N 810  3 using namespace std;  4 typedef long long ll;  5 inline int read()  6 {  7     int x=0,f=1; char ch=getchar();  8     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}  9     while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 10     return x*f; 11 } 12 struct edge{
   int u,v,w;}mps[N][N]; 13 int n,m,mat[N],pre[N],bl[N],fa[N],tim;ll totw=0; 14 int sign[N],lab[N],slacku[N],blofm[N][N],tot,mx; 15 vector 
      
        leaves[N]; 16 int q[N],hd; 17 inline int calc_e(const edge &e) 18 { 19     return lab[e.u]+lab[e.v]-mps[e.u][e.v].w*2; 20 } 21 inline void updata(int u,int x) 22 { 23     if(!slacku[x]||calc_e(mps[u][x])
       
        0&&fa[i]!=x&&sign[fa[i]]==0) 31             updata(i,x); 32 } 33 inline void q_push(int x) 34 { 35     if(x<=n) q[++hd]=x; 36     else for(int i=0;i<(int)leaves[x].size();i++) 37         q_push(leaves[x][i]);  38 } 39 inline int get_lca(int x, int y) 40 { 41     if(tim=100000000)  42         memset(bl,0,sizeof bl),tim=0; 43     for(++tim;x||y;swap(x,y)) if(x) 44     { 45         if(bl[x]==tim) return x; 46         bl[x]=tim; x=fa[mat[x]]; 47         if(x) x=fa[pre[x]]; 48     } 49     return 0; 50 } 51 inline void set_fa(int x,int y) 52 { 53     fa[x]=y; if(x>n)  54     for(int i=0;i<(int)leaves[x].size();i++) 55         set_fa(leaves[x][i],y); 56 } 57 inline void set_mat(int x,int y) 58 { 59     mat[x]=mps[x][y].v; 60     if(x<=n) return ; 61     int xr=blofm[x][mps[x][y].u]; 62     int pr=find(leaves[x].begin(),leaves[x].end(),xr)-leaves[x].begin(); 63     if(pr%2==1) 64         reverse(leaves[x].begin()+1, leaves[x].end()), 65         pr=(int)leaves[x].size()-pr; 66     for(int i=0;i
        
         n&&!lab[leaves[x][i]]) 76             blossom_blooms(leaves[x][i]); 77         else set_fa(leaves[x][i],leaves[x][i]); 78     } 79     fa[x]=0; 80 } 81 inline void blossom_make(int u,int lca,int v) 82 { 83     int x=n+1; while(x<=tot&&fa[x]) x++; 84     if(x>tot) tot++;  85     lab[x]=sign[x]=0; 86     mat[x]=mat[lca]; leaves[x].clear(); 87     leaves[x].push_back(lca); 88     for(int i=u;i!=lca;i=fa[pre[fa[mat[i]]]]) 89         leaves[x].push_back(i),leaves[x].push_back(fa[mat[i]]),q_push(fa[mat[i]]); 90     reverse(leaves[x].begin()+1, leaves[x].end()); 91     for(int i=v;i!=lca;i=fa[pre[fa[mat[i]]]]) 92         leaves[x].push_back(i),leaves[x].push_back(fa[mat[i]]),q_push(fa[mat[i]]); 93     set_fa(x,x); 94     for(int i=1;i<=tot;i++) 95         mps[x][i].w=mps[i][x].w=0, blofm[x][i]=0; 96     for(int i=0;i<(int)leaves[x].size();i++) 97     { 98         int xs=leaves[x][i]; 99         for(int j=1;j<=tot;j++)100             if(!mps[x][j].w||calc_e(mps[xs][j])
         
          0&&fa[lx]!=fa[j])181                 {182                     if(!calc_e(mps[lx][j]))183                     {184                         if(deal_edge(mps[lx][j])) 185                             return 1;186                     }187                     else if(sign[fa[j]]!=1) updata(lx,fa[j]);188                 }189         }190         int d=0x3fffffff;191         for(int i=1;i<=n;i++) if(!sign[fa[i]])192             d=min(d,lab[i]);193         for(int i=n+1;i<=tot;i++)194             if(fa[i]==i&&sign[i]==1)195                 d=min(lab[i]/2,d);196         for(int i=1;i<=tot;i++) if(fa[i]==i&&slacku[i])197         {198             if(sign[i]==-1) d=min(calc_e(mps[slacku[i]][i]),d);199             else if(sign[i]==0) d=min(calc_e(mps[slacku[i]][i])/2,d);200         }201         for(int i=1;i<=n;i++)202             if(sign[fa[i]]==0) lab[i]-=d;203             else if (sign[fa[i]]==1) lab[i]+=d;204         for(int i=n+1;i<=tot;i++)205             if(fa[i]==i)206             {207                 if(sign[i]==0) lab[i]+=d*2; 208                 else if(sign[i]==1) lab[i]-=d*2;209             }210         hd=0;211         for(int i=1;i<=n;i++) if(!lab[i]) return 0; //all vetices matched,single vetices's label = 0212         for(int i=1;i<=tot;i++)213             if(fa[i]==i&&slacku[i]&&fa[slacku[i]]!=i&&calc_e(mps[slacku[i]][i])==0)214                 /*new edge*/ if(deal_edge(mps[slacku[i]][i])) return 1;215         for(int i=n+1;i<=tot;i++)216             if(fa[i]==i&&sign[i]==1&&!lab[i])217                 blossom_bloom_1(i);218     }219     return 0;220 }221 inline void solve()222 {223     for(int i=1;i<=n;i++) mat[i]=0;224     tot=n; hd=totw=0;  225     for(int i=0;i<=n;i++) fa[i]=i,leaves[i].clear();226     for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)227         blofm[i][j]=(i==j? i:0);228     for(int i =1;i<=n;i++) lab[i]=mx; //init label229     while(match());230     for(int i=1;i<=n;i++) if(mat[i]&&mat[i]
         
        
       
      
     

代码量简直了