匈牙利算法（codevs2776）

type node=^link;
link=record
des:longint;
next:node;
end;
var
n,m,i,t,num:longint;
p:node;
nd:array[1..200] of node;
mat:array[1..200] of longint;
vis:array[1..200]
of boolean;
sel:array[1..200] of longint;
function find(po:longint):boolean;
var
p:node;
begin
p:=nd[po];
while p<>nil do
begin
if vis[p^.des]=false then
begin
vis[p^.des]:=true;
if sel[p^.des]=0 then
begin
sel[p^.des]:=po;
mat[po]:=p^.des;
exit(true);
end else
if find(sel[p^.des])=true then
begin
sel[p^.des]:=po;
mat[po]:=p^.des;
exit(true);
end;
end;
p:=p^.next;
end;
exit(false);
end;
begin
read(n,m);
for i:=1 to n do
begin
read(t);
while t<>0 do
begin
new(p);p^.next:=nd[t];p^.des:=i;nd[t]:=p;
read(t);
end;
end;
for i:=1 to m do
if mat[i]=0 then
begin
fillchar(vis,sizeof(vis),0);
if find(i) then inc(num);
end;
writeln(num);
end.

c++

-------------------------------------------------------------------------------------------

BZOJ1059

#include <cstdio>
int nd[201],next[100001],bt[201],des[100001],sel[201],mat[201],n,cnt;
int dfs(int po){
for (int p=nd[po];p!=-1;p=next[p])
if (bt[des[p]]==0){
bt[des[p]]=1;
if (sel[des[p]]==-1||dfs(sel[des[p]])){
sel[des[p]]=po;
mat[po]=des[p];
return(1);
}
}
return(0);
}
int Hung(){
for (int i=1;i<=n;i++) sel[i]=-1;
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++) bt[j]=0;
if (!dfs(i)) return(0);
}
return(1);
}
void addedge(int x,int y){
next[++cnt]=nd[x];des[cnt]=y;nd[x]=cnt;
}
int main(){
int T;
scanf("%d",&T);
while (T--){
cnt=0;
scanf("%d",&n);
for (int i=1;i<=n;i++) nd[i]=-1;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
int t;
scanf("%d",&t);
if (t) addedge(i,j);
}
if (Hung()) printf("Yesn");else printf("Non");
}
}

 

 

另外，

最小点覆盖数=最大匹配数 
最大独立集=顶点数-最大匹配数
最小路径覆盖数 = 顶点数 - 最大匹配数

_____________________________________________

BZOJ1443

确定一个点是否为匹配的必选点，后手走匹配边

（确定必选边BZOJ2140）

#include <cstdio>
#include <map>
using namespace std;
map <int,int> mp;
const int dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
int n,m,b[101][101],ndx[10101],ndy[10101],next[1000001],des[1000001];
int vis[10101],sel[10101],mat[10101],dfstim,xcnt,ycnt,cnt,ans[10101][2];
char st[110];
void addedgex(int x,int y){
next[++cnt]=ndx[x];des[cnt]=y;ndx[x]=cnt;
}
void addedgey(int x,int y){
next[++cnt]=ndy[x];des[cnt]=y;ndy[x]=cnt;
}
int ok(int x,int y){
return(x&&y&&x<=n&&y<=m&&b[x][y]);
}
int dfs(int po){
for (int p=ndx[po];p!=-1;p=next[p])
if (!vis[des[p]]){
vis[des[p]]=1;
if (sel[des[p]]==0||dfs(sel[des[p]])){
mat[po]=des[p];sel[des[p]]=po;
return(1);
}
}
return(0);
}
int checkx(int po){
vis[po]=dfstim;
if (!mat[po]) return(1);
for (int p=ndy[mat[po]];p!=-1;p=next[p])
if (vis[des[p]]<dfstim)
if (checkx(des[p])) return(1);
return(0);
}
int checky(int po){
vis[po]=dfstim;
if (!sel[po]) return(1);
for (int p=ndx[sel[po]];p!=-1;p=next[p])
if (vis[des[p]]<dfstim)
if (checky(des[p])) return(1);
return(0);
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%s",&st);
for (int j=1;j<=m;j++)
if (st[j-1]=='.'){
b[i][j]=1;
if (((i+j)&1)==0){
mp[i*500+j]=++xcnt;
}else{
mp[i*500+j]=++ycnt;
}
}
}
for (int i=1;i<=xcnt;i++) ndx[i]=-1;
for (int i=1;i<=ycnt;i++) ndy[i]=-1;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
if (b[i][j]&&(((i+j)&1)==0))
for (int k=0;k<4;k++)
if (ok(i+dir[k][0],j+dir[k][1]))
addedgex(mp[i*500+j],mp[(i+dir[k][0])*500+j+dir[k][1]]),
addedgey(mp[(i+dir[k][0])*500+j+dir[k][1]],mp[i*500+j]);
for (int i=1;i<=xcnt;i++){
for (int j=1;j<=ycnt;j++) vis[j]=0;
dfs(i);
}
cnt=0;dfstim=1;
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
if (b[i][j]){
dfstim++;
int po=mp[i*500+j];
if (((i+j)&1)==0){
if (checkx(po)){
cnt++;
ans[cnt][0]=i;ans[cnt][1]=j;
}
}else
if (checky(po)){
cnt++;
ans[cnt][0]=i;ans[cnt][1]=j;
}
}
if (cnt) printf("WINn");else printf("LOSEn");
for (int i=1;i<=cnt;i++)
printf("%d %dn",ans[i][0],ans[i][1]);
}

 ——————————————————————————————

霍尔定理

二部图G中的两部分顶点组成的集合分别为X, Y, X={X1, X2, X3,X4, .........,Xm}　, Y={y1, y2, y3, y4 , .........,yn},G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：　X中的任意k个点至少与Y中的k个点相邻。

TCO15 Round 1A Revmatching

You have a weighted bipartite graph. Each partition contains n vertices numbered 0 through n-1. You are given the weights of all edges encoded into a vector <string> A with n elements, each containing n characters. For each i and j, A[i][j] is '0' if there is no edge between vertex i in the first partition and vertex j in the second partition. Otherwise, A[i][j] is between '1' and '9', inclusive, and the digit represents the weight of the corresponding edge.

 

A perfect matching is a permutation p of 0 through n-1 such that for each i there is an edge (of any positive weight) between vertex i in the first partition and vertex p[i] in the second partition.

 

Your goal is to have a graph that does not contain any perfect matching. You are allowed to delete edges from your current graph. You do not care about the number of edges you delete, only about their weights. More precisely, you want to reach your goal by deleting a subset of edges with the smallest possible total weight. Compute and return the total weight of deleted edges in an optimal solution.

枚举每个X的子集，设其包含k个元素。断开若干点后使得Y中仅有k-1个元素。将断开点的价值求出后排序即可

int smallest(vector <string> A){
int n=A.size();
int ans=1e9;
for (int i=1;i<1<<n;i++){
for (int j=1;j<=n;j++) sum[j]=0;
for (int j=1;j<=n;j++)
if (i&(1<<(j-1)))
for (int k=1;k<=n;k++)
sum[k]+=A[j-1][k-1]-'0';
sort(sum+1,sum+n+1);
int t=bitcount(i),tsum=0;
for (int j=1;j<=n-t+1;j++) tsum+=sum[j];
ans=min(ans,tsum);
}
return(ans);
}