二分图判定:
dfs:
const int __=10005;
bool flag;
int col[__];
vector<int>G[__];
void dfs(int x,int y)
{
if(col[x])
{
if(col[x]!=y)flag=false;
return;
}
col[x]=y;
for(int i=0; i<G[x].size() && flag; i++)
dfs(G[x][i],3-y);
}
void init(void)
{
memset(col,0,sizeof(col));
flag=true;
}
int main()
{
int _;
scanf("%d",&_);
while(_--)
{
init();
int n,m;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1; i<=n; i++)
if(!col[i])dfs(i,1);
if(flag)printf("Correct\n");
else printf("Wrong\n");
for(int i=1;i<=n;i++)G[i].clear();
}
return 0;
}
最大匹配:
dfs:
vector<int>G[1005];
bool vis[1005];
int m,n;
int match[1005];
bool dfs(int x)
{
int len=G[x].size();
for(int i=0; i<len; i++)
{
int nex=G[x][i];
if(!vis[nex])
{
vis[nex]=true;
if(!match[nex]||dfs(match[nex]))
{
match[nex]=x;
match[x]=nex;
return true;
}
}
}
return false;
}
int main()
{
int x,y,ans=0;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
if(!match[i]&&dfs(i))ans++;
}
printf("%d\n",ans);
for(int i=1;i<=n;i++)G[i].clear();
return 0;
}
二维最大匹配:
struct point
{
int x,y;
};
char maze[50][50];
bool vis[50][50];
int m,n;
vector<point>vec[50][50];
point match[50][50];
void judgepoint(int x,int y)
{
point t;
if(x>1&&maze[x-1][y]=='*')
{
t.x=x-1;
t.y=y;
vec[x][y].push_back(t);
}
if(x<m&&maze[x+1][y]=='*')
{
t.x=x+1;
t.y=y;
vec[x][y].push_back(t);
}
if(y>1&&maze[x][y-1]=='*')
{
t.x=x;
t.y=y-1;
vec[x][y].push_back(t);
}
if(y<n&&maze[x][y+1]=='*')
{
t.x=x;
t.y=y+1;
vec[x][y].push_back(t);
}
}
bool dfs(int x,int y)
{
int len=vec[x][y].size();
for(int i=0; i<len; i++)
{
point temp=vec[x][y][i];
if(!vis[temp.x][temp.y])
{
vis[temp.x][temp.y]=1;
if((!match[temp.x][temp.y].x&&!match[temp.x][temp.y].y)
||dfs(match[temp.x][temp.y].x,match[temp.x][temp.y].y))
{
match[temp.x][temp.y].x=x;
match[temp.x][temp.y].y=y;
match[x][y].x=temp.x;
match[x][y].y=temp.y;
return true;
}
}
}
return false;
}
void init(void)
{
memset(maze,0,sizeof(maze));
memset(match,0,sizeof(match));
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init();
scanf("%d%d",&m,&n);
for(int i=1; i<=m; i++)
scanf("%s",maze[i]+1);
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
if(maze[i][j]=='*')
judgepoint(i,j);
int ans=0;
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
if(maze[i][j]=='*'&&!match[i][j].x&&!match[i][j].y)
{
memset(vis,0,sizeof(vis));
if(dfs(i,j))ans++;
}
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
if(maze[i][j]=='*'&&!match[i][j].x&&!match[i][j].y)
ans++;
printf("%d\n",ans);
for(int i=1; i<=m; i++)
for(int j=1; j<=n; j++)
if(maze[i][j]=='*')vec[i][j].clear();
}
return 0;
}
最小点覆盖=最大匹配数
最大独立集=点数-最大匹配数
vector<int>G[1005];
bool vis[1005];
int m,n;
int match[1005];
bool dfs(int x)
{
int len=G[x].size();
for(int i=0; i<len; i++)
{
int nex=G[x][i];
if(!vis[nex])
{
vis[nex]=true;
if(!match[nex]||dfs(match[nex]))
{
match[nex]=x;
match[x]=nex;
return true;
}
}
}
return false;
}
int main()
{
int x,y,ans=0;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
if(!match[i]&&dfs(i))ans++;
}
printf("%d\n%d\n",ans,n-ans);
for(int i=1;i<=n;i++)G[i].clear();
return 0;
}
最小路径覆盖=点数-最大匹配数
vector<int>G[1005];
bool vis[1005];
int match[1005];
bool dfs(int x)
{
int len=G[x].size();
for(int i=0; i<len; i++)
{
int nex=G[x][i];
if(!vis[nex])
{
vis[nex]=true;
if(!match[nex]||dfs(match[nex]))
{
match[nex]=x;
match[x]=nex;
return true;
}
}
}
return false;
}
int main()
{
int n,m,x,y,ans=0;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
G[x].push_back(n+y);
}
for(int i=1;i<=n;i++)
{
memset(vis,false,sizeof(vis));
if(!match[i]&&dfs(i))ans++;
}
printf("%d\n",n-ans);
return 0;
}
km:
int cost[305][305],lx[305],ly[305];
int match[305],d;
bool visx[305],visy[305];
bool dfs(int x,int ny)
{
visx[x]=true;
for(int y=1; y<=ny; y++)
{
if(visy[y])continue;
int t=lx[x]+ly[y]-cost[x][y];
if(!t)
{
visy[y]=true;
if(!match[y] || dfs(match[y],ny))
return match[y]=x;
}
else d=min(d,t);
}
return false;
}
int km(int nx,int ny)
{
memset(lx,0,sizeof(lx));
memset(ly,0,sizeof(ly));
memset(match,0,sizeof(match));
for(int i=1; i<=nx; i++)
for(int j=1; j<=ny; j++)
lx[i]=max(lx[i],cost[i][j]);
for(int x=1; x<=nx; x++)
while(1)
{
d=inf;
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
if(dfs(x,ny))break;
if(d==inf)return -1;
for(int x=1; x<=nx; x++)
if(visx[x])lx[x]-=d;
for(int y=1; y<=ny; y++)
if(visy[y])ly[y]+=d;
}
int res=0;
for(int y=1; y<=ny; y++)
if(match[y])
res+=cost[match[y]][y];
return res;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
scanf("%d",&cost[i][j]);
printf("%d\n",km(n,n));
}
return 0;
}
