[WC2016]挑战NPC(一般图最大匹配)
题解时间
思路十分有趣。
考虑一个筐只有不多于一个球才有1的贡献代表什么。
很明显等效于有至少两个位置没有被匹配时有1的贡献。
进而可以构造如下模型：
每个筐拆成三个点，三个点之间相互连边。
对于球可以匹配某个筐，将球向筐的三个点都连边。
这样一来，如果有一个筐只有不多于一个点被匹配，那么剩下的两个点可以自己匹配增加答案。
如此最终结果是 $ ans-n $ 。
需要用到一般图最大匹配也即带花树。
由于答案要求输出匹配方案，所以要注意先匹配球再匹配筐。
#include<bits/stdc++.h>
using namespace std;
typedef long long lint;
struct pat{int x,y;pat(int x=0,int y=0):x(x),y(y){}bool operator<(const pat &p)const{return x==p.x?y<p.y:x<p.x;}};
template<typename TP>inline void read(TP &tar)
{
TP ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=ret*10+(ch-'0');ch=getchar();}
tar=ret*f;
}
namespace RKK
{
const int N=1011,M=300011;
struct sumireko{int to,ne;}e[M];int he[N],ecnt;
void addline(int f,int t){e[++ecnt].to=t;e[ecnt].ne=he[f],he[f]=ecnt;}
int n,m,o,tar[N];
int f[N];int find(int x){return f[x]==f[f[x]]?f[x]:f[x]=find(f[x]);}
int dep[N],da;
int pre[N],col[N];
queue<int>q;
int lca(int x,int y)
{
da++;x=find(x),y=find(y);
while(dep[x]!=da){dep[x]=da,x=find(pre[tar[x]]);if(y) swap(x,y);}
return x;
}
void uno(int x,int y,int z)
{
while(find(x)!=z)
{
pre[x]=y,y=tar[x];
if(col[y]==2) col[y]=1,q.push(y);
if(find(x)==x) f[x]=z;if(find(y)==y) f[y]=z;
x=pre[y];
}
}
int hun(int sp)
{
memset(col,0,sizeof(col)),memset(pre,0,sizeof(pre));
for(int i=1;i<=n+m*3;i++) f[i]=i;while(!q.empty()) q.pop();
q.push(sp),col[sp]=1;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=he[x],t=e[i].to;i;i=e[i].ne,t=e[i].to)if(col[t]!=2&&find(x)!=find(t))
{
if(!col[t])
{
col[t]=2,pre[t]=x;
if(!tar[t])
{
int lst=0;while(t) lst=tar[pre[t]],tar[t]=pre[t],tar[pre[t]]=t,t=lst;
return 1;
}else col[tar[t]]=1,q.push(tar[t]);
}else{int z=lca(x,t);uno(x,t,z),uno(t,x,z);}
}
}
return 0;
}
int main()
{
int TAT;read(TAT);while(TAT--)
{
read(n),read(m),read(o);
for(int i=1;i<=m;i++)
addline(i,m+i),addline(m+i,i),addline(m+i,m*2+i),addline(m*2+i,m+i),addline(m*2+i,i),addline(i,m*2+i);
for(int i=1,x,y;i<=o;i++)
read(x),read(y),
addline(m*3+x,y),addline(y,m*3+x),
addline(m*3+x,m+y),addline(m+y,m*3+x),
addline(m*3+x,m*2+y),addline(m*2+y,m*3+x);
int ans=0;
for(int i=m*3+1;i<=m*3+n;i++)if(!tar[i]) ans+=hun(i);
for(int i=1;i<=m*3;i++)if(!tar[i]) ans+=hun(i);
printf("%d
",ans-n);
for(int i=1;i<=n;i++) printf("%d ",(tar[m*3+i]-1)%m+1);putchar('
');
memset(he,0,sizeof(he)),ecnt=0,memset(dep,0,sizeof(dep)),da=0,memset(tar,0,sizeof(tar));
}
return 0;
}
}
int main(){return RKK::main();}