还差一个一般图最大权匹配貌似就差不多了= =

匹配题目做得少，只好意思贴贴模板= =

Hungary（貌似没有网络流跑得快）：

#include <iostream>
#include <string.h>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 505
int a[N][N],c[N],n,m,s;
bool b[N];
inline bool aa(int x)
 {
 	int i;
 	for (i=1;i<=n;i++)
 	 if (a[x][i] && !b[i])
 	  {
 	  	 b[i]=1;
 	  	 if (!c[i] || aa(c[i]))
 	  	  {
 	  	  	 c[i]=x;
 	  	  	 return 1;
 	  	  }
 	  }
 	return 0;
 }
int main()
 {
 	int i,j,k,l,q,w,e=0;
 	memset(a,0,sizeof(a));memset(c,0,sizeof(c));
 	scanf("%d%d%d",&n,&m,&s);
 	for (i=1;i<=s;i++)
 	 {
 	 	scanf("%d%d",&k,&l);
 	 	a[l][k]=1;
 	 }
 	for (i=1;i<=m;i++)
 	 {
 	 	memset(b,0,sizeof(b));
 	 	e+=aa(i);
 	 }
 	printf("%d\n",e);
 	for (i=1;i<=n;i++)
 	  printf("%d ",c[i]);
 	printf("\n");
 	return 0;
 }

KM：

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
#define N 1005
#define INF 0x3f7f7f7f
#define ll long long
struct Point
 {
 	int a1;ll a2;
 	bool operator < (const Point &x) const
 	 {
 	 	return a2<x.a2||(a2==x.a2&&a1<x.a1);
 	 }
 };
set <Point> mi;
set <Point> :: iterator it;
ll s[N],v[N][2],h[N][N],ans=0;
int p[N][2],la[N],n,m,nm;
bool b[N][2];
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
void DFS(int x)
 {
    int i=p[la[x]][0];
    if (!x) return;
    p[x][1]=la[x];p[la[x]][0]=x;
    DFS(i);
    return;
 }
void Solve(int x)
 {
    int i,j;ll q,w,e=0;Point k,l;
    while (!mi.empty())
     {
        it=mi.begin();mi.erase(it);k=*it;k.a2+=e;
        if (k.a2)
         {
            e-=k.a2;
            for (i=1;i<=nm;i++)
             if (b[i][0])
               v[i][0]-=k.a2;
            for (i=1;i<=nm;i++)
             if (b[i][1])
               v[i][1]+=k.a2;
         }
        for (i=1;i<=nm;i++)
         if (b[i][0]&&v[i][0]+v[k.a1][1]==h[i][k.a1])
           {la[k.a1]=i;break;}
        if (p[k.a1][1])
         {
            b[k.a1][1]=b[p[k.a1][1]][0]=1;
            for (i=1;i<=nm;i++)
             if (!b[i][1]&&s[i]+e>v[i][1]+v[p[k.a1][1]][0]-h[p[k.a1][1]][i])
              {
                 l.a1=i;l.a2=s[i];it=mi.lower_bound(l);mi.erase(it);
                 l.a2=s[i]=v[i][1]+v[p[k.a1][1]][0]-h[p[k.a1][1]][i]-e;
                 mi.insert(l);
              }
         }else
         {
            DFS(k.a1);return;
         }
     }
    return;
 }
int main()
 {
 	int i,j,q,w,e;ll k,l;
 	memset(s,0,sizeof(s));memset(v,0,sizeof(v));
 	memset(h,0,sizeof(h));memset(la,0,sizeof(la));
 	memset(p,0,sizeof(p));memset(b,0,sizeof(b));
 	scanf("%d%d%d",&n,&m,&e);nm=max(n,m);
 	for (i=1;i<=e;i++)
 	  h[k=Read()][Read()]=Read();
 	for (i=1;i<=nm;i++)
 	 for (j=1;j<=nm;j++)
 	   v[i][0]=max(v[i][0],h[i][j]);
 	for (i=1;i<=nm;i++)
 	 {
 	 	memset(s,0,sizeof(s));memset(b,0,sizeof(b));
 	 	mi.clear();b[i][0]=1;
 	 	for (j=1;j<=nm;j++)
 	 	  s[j]=v[j][1]+v[i][0]-h[i][j],la[j]=i,
 	 	   mi.insert((Point){j,s[j]});
 	 	Solve(i);
 	 }
 	for (i=1;i<=n;i++)
 	  ans+=p[i][0]<=m?h[i][p[i][0]]:0;
 	printf("%lld\n",ans);
 	for (i=1;i<=n;i++)
 	  printf("%d ",p[i][0]>m||!h[i][p[i][0]]?0:p[i][0]);
 	printf("\n");
 	return 0;
 }

带花树：

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 505
#define M 500050
#define INF 0x7f7f7f7f
int p[N],pre[N],c[M][2],ss=1,vis[N],sta[N],n,m,st=0,li[M];
int fi[N],ri,fa[N],ans=0;
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
inline void Line (int x,int y)
 {
 	c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
 	c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
 	return;
 }
int Find(int x)
 {
 	return fa[x]==x?x:(fa[x]=Find(fa[x]));
 }
int LCA(int x,int y)
 {
 	for (x=Find(x),y=Find(y),st++;;swap(x,y))
 	 if (x)
 	  {
 	 	 if (vis[x]==st) return x;
 	 	 vis[x]=st;x=Find(pre[p[x]]);
 	  }
 }
void Blossom(int x,int y,int z)
 {
 	while (Find(x)!=z)
 	 {
 	 	pre[x]=y;
 	 	if (sta[p[x]]==2) sta[li[++ri]=p[x]]=1;
 	 	if (fa[x]==x) fa[x]=z;
 	 	if (fa[p[x]]==p[x]) fa[p[x]]=z;
 	 	x=pre[y=p[x]];
 	 }
 	return;
 }
int Solve(int x)
 {
 	int i,j,k,l,q,w,e,le=1;
 	memset(pre,0,sizeof(pre));memset(vis,0,sizeof(vis));
 	memset(sta,0,sizeof(sta));
 	for (i=1;i<=n;i++) fa[i]=i;li[ri=sta[x]=1]=x;
 	for (;le<=ri;le++)
 	 for (i=fi[li[le]];i;i=c[i][1])
 	  if (!sta[c[i][0]])
 	   {
 	   	  sta[c[i][0]]=2;pre[c[i][0]]=li[le];
 	   	  if (!p[c[i][0]])
 	   	   {
 	   	   	  for (k=c[i][0];k;)
 	   	   	    l=p[pre[k]],p[k]=pre[k],p[p[k]]=k,k=l;
 	   	   	  return 1;
 	   	   }
 	   	  sta[li[++ri]=p[c[i][0]]]=1;
 	   }else
 	  if (sta[c[i][0]]==1&&Find(c[i][0])!=Find(li[le]))
 	    j=LCA(li[le],c[i][0]),Blossom(li[le],c[i][0],j),
 	     Blossom(c[i][0],li[le],j);
 	return 0;
 }
int main()
 {
 	int i,j,k,l,q,w,e;
 	scanf("%d%d",&n,&m);
 	for (i=1;i<=m;i++)
 	  Line(Read(),Read());
 	for (i=1;i<=n;i++)
 	 if (!p[i]) ans+=Solve(i);
 	printf("%d\n",ans);
 	for (i=1;i<=n;i++)
 	  printf("%d ",p[i]);
 	printf("\n");
 	return 0;
 }

这些都可以在UOJ模板题库里面找到。