Strategic game(无向?)二分图最小点覆盖(Poj1463,Uva1292)
原题链接
此题求二分图的最小点覆盖，数值上等于该二分图的最大匹配。得知此结论可以将图染色，建有向图，然后跑匈牙利/网络流,如下。然而...
#include
#include
#include
using namespace std;
const int MAXN=2000+5;
int q[MAXN],hd1[MAXN],hd2[MAXN];
int lnk[MAXN];
bool vis[MAXN],bw[MAXN];
int n,ft,rr,cnt1,cnt2;
struct Edge
{
int t,n;
}e1[MAXN<<1],e2[MAXN<<1];
inline void build(int f,int t)
{
e1[++cnt1]=(Edge){t,hd1[f]};
hd1[f]=cnt1;
}
inline void build2(int f,int t)
{
e2[++cnt2]=(Edge){t,hd2[f]};
hd2[f]=cnt2;
}
void bfs()
{
ft=rr=0;
memset(bw,0,sizeof bw);
memset(vis,0,sizeof vis);
q[rr++]=0;
vis[0]=1;
bw[0]=1;
while(ft 然而我看网络上流传的都是另一种做法，直接输出在原无向图的最大匹配除以2，却很少有人证明（可能是各位大佬都认为这太显然了不用证）。仔细思考这个结论还是比较显然的（虽然我还想了一会），这里给出简单的证明，原来匹配一次的边被分别从从左右两个方向匹配了一次，这样每天匹配边就被记录了两次，又因为是求得的是最大匹配数，所以左右两边的匹配都应是最大匹配，故求给定无向图求最大匹配可以直接在原图求最大匹配，答案为该数值除以2。
#include
#include
#include
using namespace std;
const int MAXN=2000+5;
int hd[MAXN],lnk[MAXN];
bool vis[MAXN];
int n,cnt;
struct Edge
{
int t,n;
}e[MAXN<<1];
inline void build(int f,int t)
{
e[++cnt]=(Edge){t,hd[f]};
hd[f]=cnt;
}
bool match(int u)
{
for(int i=hd[u];i;i=e[i].n)
{
int v=e[i].t;
if(!vis[v])
{
vis[v]=1;
if(lnk[v]==-1||match(lnk[v]))
{
lnk[v]=u;
return 1;
}
}
}
return 0;
}
int main()
{
while(~scanf("%d",&n))
{
cnt=0;
memset(hd,0,sizeof hd);
memset(e,0,sizeof e);
memset(lnk,-1,sizeof lnk);
int from,m,to;
for(int i=0;i>1);
}
return 0;
}
还有DP解法，待填。
11.02UPD 树形DP解法