匈牙利算法（codevs2776）
type node=^link;
link=record
des:longint;
next:node;
end; var
n,m,i,t,num:longint;
p:node;
nd:array[..] of node;
mat:array[..] of longint;
vis:array[..] of boolean;
sel:array[..] 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]= 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:= to n do
begin
read(t);
while t<> do
begin
new(p);p^.next:=nd[t];p^.des:=i;nd[t]:=p;
read(t);
end;
end; for i:= to m do
if mat[i]= then
begin
fillchar(vis,sizeof(vis),);
if find(i) then inc(num);
end; writeln(num); end.
c++
-------------------------------------------------------------------------------------------
BZOJ1059
#include <cstdio>
int nd[],next[],bt[],des[],sel[],mat[],n,cnt;
int dfs(int po){
for (int p=nd[po];p!=-;p=next[p])
if (bt[des[p]]==){
bt[des[p]]=;
if (sel[des[p]]==-||dfs(sel[des[p]])){
sel[des[p]]=po;
mat[po]=des[p];
return();
}
}
return();
}
int Hung(){
for (int i=;i<=n;i++) sel[i]=-;
for (int i=;i<=n;i++){
for (int j=;j<=n;j++) bt[j]=;
if (!dfs(i)) return();
}
return();
}
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=;
scanf("%d",&n);
for (int i=;i<=n;i++) nd[i]=-;
for (int i=;i<=n;i++)
for (int j=;j<=n;j++){
int t;
scanf("%d",&t);
if (t) addedge(i,j);
}
if (Hung()) printf("Yes\n");else printf("No\n");
}
}
另外，
最小点覆盖数=最大匹配数
最大独立集=顶点数-最大匹配数
最小路径覆盖数 = 顶点数 - 最大匹配数
_____________________________________________
BZOJ1443
确定一个点是否为匹配的必选点，后手走匹配边
（确定必选边BZOJ2140）
#include <cstdio>
#include <map>
using namespace std; map <int,int> mp; const int dir[][]={{-,},{,-},{,},{,}}; int n,m,b[][],ndx[],ndy[],next[],des[];
int vis[],sel[],mat[],dfstim,xcnt,ycnt,cnt,ans[][];
char st[]; 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!=-;p=next[p])
if (!vis[des[p]]){
vis[des[p]]=;
if (sel[des[p]]==||dfs(sel[des[p]])){
mat[po]=des[p];sel[des[p]]=po;
return();
}
}
return();
} int checkx(int po){
vis[po]=dfstim;
if (!mat[po]) return();
for (int p=ndy[mat[po]];p!=-;p=next[p])
if (vis[des[p]]<dfstim)
if (checkx(des[p])) return();
return();
} int checky(int po){
vis[po]=dfstim;
if (!sel[po]) return();
for (int p=ndx[sel[po]];p!=-;p=next[p])
if (vis[des[p]]<dfstim)
if (checky(des[p])) return();
return();
} int main(){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++){
scanf("%s",&st);
for (int j=;j<=m;j++)
if (st[j-]=='.'){
b[i][j]=;
if (((i+j)&)==){
mp[i*+j]=++xcnt;
}else{
mp[i*+j]=++ycnt;
}
}
} for (int i=;i<=xcnt;i++) ndx[i]=-;
for (int i=;i<=ycnt;i++) ndy[i]=-;
for (int i=;i<=n;i++) for (int j=;j<=m;j++)
if (b[i][j]&&(((i+j)&)==))
for (int k=;k<;k++)
if (ok(i+dir[k][],j+dir[k][]))
addedgex(mp[i*+j],mp[(i+dir[k][])*+j+dir[k][]]),
addedgey(mp[(i+dir[k][])*+j+dir[k][]],mp[i*+j]); for (int i=;i<=xcnt;i++){
for (int j=;j<=ycnt;j++) vis[j]=;
dfs(i);
} cnt=;dfstim=;
for (int i=;i<=n;i++) for (int j=;j<=m;j++)
if (b[i][j]){
dfstim++;
int po=mp[i*+j];
if (((i+j)&)==){
if (checkx(po)){
cnt++;
ans[cnt][]=i;ans[cnt][]=j;
}
}else
if (checky(po)){
cnt++;
ans[cnt][]=i;ans[cnt][]=j;
}
} if (cnt) printf("WIN\n");else printf("LOSE\n");
for (int i=;i<=cnt;i++)
printf("%d %d\n",ans[i][],ans[i][]);
}
——————————————————————————————
霍尔定理
二部图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=;i<<<n;i++){
for (int j=;j<=n;j++) sum[j]=;
for (int j=;j<=n;j++)
if (i&(<<(j-)))
for (int k=;k<=n;k++)
sum[k]+=A[j-][k-]-'';
sort(sum+,sum+n+);
int t=bitcount(i),tsum=;
for (int j=;j<=n-t+;j++) tsum+=sum[j];
ans=min(ans,tsum);
}
return(ans);
}
最新文章
- Python语言特性之2：元类
- ASP.NET文件上传大小的限制解决方案
- POJ 题目分类（转载）
- 【No.5 Ionic】修改 应用名，icon，启动界面
- 模块化InnoSetup依赖项安装
- Shell script for logging cpu and memory usage of a Linux process
- OGR API Tutorial
- Java新手如何学习Spring、Struts、Hibernate三大框架？（转）
- Python 面向对象高阶-----metaclass
- JAVA实现C/S结构小程序
- 【MYSQL】MYSQL报错解决方法： Warning: (3719, "'utf8' is currently an alias for the character set UTF8MB3, but will be an alias for UTF8M B4 in a future release."
- PeopleSoft如何查找jar包冲突
- 2018-2019-2 20175310 实验二《Java面向对象程序设计》实验报告
- 关闭Android ActionBar
- service cloudera-scm-server restart报错 Unable to retrieve remote parcel repository manifest
- 64位版本为什么叫amd64，而不是intel64
- 编译安装nginx，并使用systemd管理nginx
- 最全的前端Git基础命令，看完保证你会！
- Android中windowTranslucentStatus与windowTranslucentNavigation的一些设置(转)
- Failed to execute goal org.apache.maven.plugins:maven-clean-plugin:2.5:clean (default-clean)