题解 P3967 【[TJOI2014]匹配】
龙翔凤翥
2019-09-24 20:15:53
### solution：
先考虑第一问，求最大幸福值，显然是二分图带权最大匹模板。直接用**KM**算法。那么如何解决最大匹配后二分图的交集呢？
1. 首先，我是这样想的：如果存在多个最大二分图带权匹配，那么对于处于交集中的男朋友他连向女朋友的那一条边一定是独一无二的，不然他就能够选择另一条权值一样的边连向另一个女朋友，这样就不在交集中了。显然这个想法是片面的，但是跟正解搭上边了。
2. 对于一对在交集中的男女朋友，虽然最大匹配有多个，但这一对男女朋友是会变的，说明这一对男女朋友在匹配中始终是最优解，那么如果把这一对男女朋友的边权值改为0，那么最大匹配的权值和一定会变。在看数据范围N<=80,N^4的复杂度能够接受。所以我们便想到先KM一遍算出最大匹配值，再对每一个男朋友询问他跟哪一个女朋友牵红线，将这条边权改为0，（不必对每一条边都修改，应为那些边不都是最优的边），看最后的最大匹配值是否变小，若不变，则这对男女朋友不在交集中，反之，则在。
3. ****细节注意****： 见代码。
### code：
```
#include<bits/stdc++.h>
using namespace std;
#define RN register int
inline int read()
{
int k=1,x=0;
char ch;
ch=getchar();
while(ch<'0'||ch>'9'&&ch!='-')
ch=getchar();
while(ch=='-')
k=-1,ch=getchar();
while(ch>='0'&&ch<='9')
x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*k;
}
int n;
int la[500],lb[500],va[500],vb[500];
int match[500],match2[500],w[100][100],data;
int sum=-1;
struct P{
int l;
int r;
}h[500];
inline int cmp(P x,P y)
{
return x.l<y.l;
}
inline bool dfs(int x)
{
va[x]=1;
for(RN y=1;y<=n;y++)
{
if(!vb[y])
if(la[x]+lb[y]-w[x][y]==0)
{
vb[y]=1;
if(!match[y]||dfs(match[y]))
{
match[y]=x;
return true;
}
}
else data=min(data,la[x]+lb[y]-w[x][y]);
}
return false;
}
inline int km()//用来求修改之前的匹配最大权值，即第一问答案。
{
for(RN i=1;i<=n;i++)
{
la[i]=-(1<<30);
lb[i]=0;
for(RN j=1;j<=n;j++)
la[i]=max(la[i],w[i][j]);
}
for(RN k=1;k<=n;k++)
{
while(233)
{
memset(va,0,sizeof(va));
memset(vb,0,sizeof(vb));
data=1<<30;
if(dfs(k))
break;
/* for(RN j=1;j<=n;j++)
if(!vb[j])
data=min(data,la[k]+lb[j]-w[k][j]);*/
for(RN i=1;i<=n;i++)
{
if(va[i])
la[i]-=data;
if(vb[i])
lb[i]+=data;
}
}
}
int ans=0;
for(RN i=1;i<=n;i++)
ans+=w[match[i]][i];
return ans;
}
inline bool dfs2(int x)
{
va[x]=1;
for(RN y=1;y<=n;y++)
{
if(!vb[y])
if(la[x]+lb[y]-w[x][y]==0)
{
vb[y]=1;
if(!match2[y]||dfs2(match2[y]))
{
match2[y]=x;
return true;
}
}
else
data=min(data,la[x]+lb[y]-w[x][y]);
}
return false;
}
inline int km2()//处理修改后的匹配最大值。
{
for(RN i=1;i<=n;i++)
{
la[i]=-(1<<30);
lb[i]=0;
for(RN j=1;j<=n;j++)
la[i]=max(la[i],w[i][j]);
}
for(RN k=1;k<=n;k++)
{
while(233)
{
memset(va,0,sizeof(va));
memset(vb,0,sizeof(vb));
data=1<<30;
if(dfs2(k))
break;
/* for(RN j=1;j<=n;j++)
if(!vb[j])
data=min(data,la[k]+lb[j]-w[k][j]);
*/for(RN i=1;i<=n;i++)
{
if(va[i])
la[i]-=data;
if(vb[i])
lb[i]+=data;
}
}
}
int ans2=0;
for(RN i=1;i<=n;i++)
ans2+=w[match2[i]][i];
return ans2;
}
int main()
{
// freopen("1.out","r",stdin);
// freopen("ans.out","w",stdout);
n=read();
for(RN i=1;i<=n;i++)
for(RN j=1;j<=n;j++)
w[i][j]=read();
//for(RN i=1;i<=5000;i++)
// h[i].val=0;
int sum=km();
cout<<sum<<endl;
int tot=0;
for(RN i=1;i<=n;i++)
{
int tmp=w[match[i]][i];//修改这个男朋友到女朋友的边权值
w[match[i]][i]=0;
memset(match2,0,sizeof(match2));//注意匹配对象要清零
if(km2()<sum)//修改后发现答案变小了，说明这对男女在交集中
h[++tot].r=i,h[tot].l=match[i];
w[match[i]][i]=tmp;
}
sort(h+1,h+tot+1,cmp);
for(RN i=1;i<=tot;i++)
cout<<h[i].l<<" "<<h[i].r<<endl;
return 0;
}