今天主要是看二分图的最优匹配内容。
有的边无权值：
对于那些原本不存在的边就赋值为负无穷.那么当我们求出最优匹配的时候,如果存在某条匹配边的权值是负无穷,那么代表本问题无解. 否则的话总权值就是最优匹配的权值解.
涉及到优先用原匹配边的问题：
例（by 饶齐）：HDU 2853 Assignment
题意:
给定一个二分图，N个点对应M个点，两两之间存在一组关系，每组关系一个权值。题目中了给定了一个匹配方案，现在要求满足这组关系中的最大的匹配权值在原方案上增长了多少？并且还要求出在原匹配方案上改变(最少)多少条边才能够得到这个最大匹配？
分析:
首先如果我们只需要求最大权值匹配，那么这道题是一个左右点集大小不对称的最优匹配问题。这里要注意KM算法模板的修改。
最优权值匹配很好求，直接用KM模板，但是要在原匹配边的基础上使得改变的边最少，这里我们这么处理：
这里由于左边点集有N个点，且M>=N。那么最终的最优匹配必然有N条边。我们让原图中的每条边的权值都乘以(N+1)，即扩大N+1倍。且如果某条边本来就是原匹配用的其中一条边，那么该边权值在扩大N+1倍后，再加1。 所以任意一条边的权值只能是N+1的倍数 或 (N+1的倍数)+1，我们将要在这种权值的边中选出N条来(想想如果我们最终在新二分图求出的最优权值和==(N+1)的倍数,那么说明什么?说明我们最优匹配中,一条老边都没有复用.虽然老边的权值有加1的优势 )。
最终我们得到的最优权值和ans除以(N+1)就是最优权值解(因为就算我们原封不动的还用以前的匹配,也就是在所有权值的基础上加了N个1,此时/(N+1),整除归0)。
最终ans%(N+1)就是我们复用旧边的条数(上述两条结论仔细验证)。
附：（个人代码）
#pragma comment(linker,"/STACK:102400000,102400000")#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>
#define maxn 310
#define INF 1e9
using namespace std;
inline int read()
{
register int c=getchar(),fg=1,sum=0;
while(c>'9'||c<'0') {if(c == '-')fg = -1;c=getchar();}
while(c<='9'&&c>='0'){sum=sum*10+c-'0';c=getchar();}
return fg*sum;
}
int n,m,k,p,ans,sum,cnt;
struct kmm{
int n,m;
int w[maxn][maxn];
int lx[maxn],ly[maxn];
int s[maxn],t[maxn];
int g[maxn];
void init(int n){}
bool dfs(int i)
{
s[i]=1;
for(int j=1;j<=m;j++)if(lx[i]+ly[j]==w[i][j]&&!t[j])
{
t[j]=true;
if(g[j]==-1||dfs(g[j]))
{
g[j]=i;
return 1;
}
}
return 0;
}
void update()
{
int a=1<<30;
for(int i=1;i<=n;i++)if(s[i])
for(int j=1;j<=m;j++)if(!t[j])
{
a=min(a,lx[i]+ly[j]-w[i][j]);
}
for(int i=1;i<=n;i++)if(s[i]) lx[i]-=a;
for(int i=1;i<=m;i++)if(t[i]) ly[i]+=a;
}
int solve(int n,int m)
{
this->n=n;
this->m=m;
memset(g,-1,sizeof(g));
memset(lx,0,sizeof(lx));
memset(ly,0,sizeof(ly));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
lx[i]=max(lx[i],w[i][j]);
}
for(int i=1;i<=n;i++)
{
while(1)
{
memset(s,0,sizeof(s));
memset(t,0,sizeof(t));
if(dfs(i)) break;
else update();
}
}
int ans=0;
for(int i=1;i<=m;i++)
if(g[i]!=-1)ans+=w[g[i]][i];
return ans;
}
}km;
int ww[maxn][maxn];
int main()
{
int r;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{scanf("%d",&ww[i][j]);
km.w[i][j]=ww[i][j]*(n+1);
}
}
cnt=0;
for(int i=1;i<=n;i++)
{
int j;
scanf("%d",&j);
cnt+=ww[i][j];
km.w[i][j]++;
}
//cout<<"*";
int cost=km.solve(n,m);
ans=((cost)%(n+1));
printf("%d %d\n",n-ans,(cost/(n+1))-cnt);
}
return 0;
}
个人二分图最优匹配模板（HDU 2255 奔小康赚大钱）：
#pragma comment(linker,"/STACK:102400000,102400000")#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<cmath>#include<vector>#define maxn 310#define INF 1e9using namespace std;inline int read(){ register int c=getchar(),fg=1,sum=0; while(c>'9'||c<'0') {if(c == '-')fg = -1;c=getchar();} while(c<='9'&&c>='0'){sum=sum*10+c-'0';c=getchar();} return fg*sum;}int n,m,k,p,ans,sum;struct kmm{int n,m;int w[maxn][maxn];int lx[maxn],ly[maxn];int s[maxn],t[maxn];int g[maxn];void init(int n){}bool dfs(int i){ s[i]=1; for(int j=1;j<=n;j++)if(lx[i]+ly[j]==w[i][j]&&!t[j]) { t[j]=true; if(g[j]==-1||dfs(g[j])) { g[j]=i; return 1; } } return 0;}void update(){ int a=1<<30; for(int i=1;i<=n;i++)if(s[i]) for(int j=1;j<=n;j++)if(!t[j]) { a=min(a,lx[i]+ly[j]-w[i][j]); } for(int i=1;i<=n;i++) { if(s[i]) lx[i]-=a; if(t[i]) ly[i]+=a; }}int solve(int n){ this->n=n; memset(g,-1,sizeof(g)); for(int i=1;i<=n;i++) { lx[i]=ly[i]=0; for(int j=1;j<=n;j++) lx[i]=max(lx[i],w[i][j]); } for(int i=1;i<=n;i++) { while(1) { for(int j=1;j<=n;j++) s[j]=t[j]=0; if(dfs(i)) break; else update(); } } int ans=0; for(int i=1;i<=n;i++) ans+=w[g[i]][i]; return ans; }}km;struct node{ int x,y; node(){} node(int xx,int yy):x(xx),y(yy){}}a1[maxn],a2[maxn];int main(){ int r; while(scanf("%d",&r)!=EOF) { for(int i=1;i<=r;i++) { for(int j=1;j<=r;j++) scanf("%d",&km.w[i][j]); } ans=km.solve(r); printf("%d\n",ans); } return 0;}