题解 P3967 【[TJOI2014]匹配】

· · 题解

写篇题解造福社会。

第一问求带权二分图的最大匹配。

模板题，直接跑KM算法或者费用流。

简述一下费用流做法：我们用节点i表示男生i，用节点n+i表示女生i，然后从节点i向节点n+j连一条容量为1，费用为H_{i,j}的边。建立超级源点和超级汇点，原点向男生连边，女生向汇点连边。最后跑最大费用最大流，总的花费即为第一问的答案。

第二位求最大费用最大流的必经边。

一个比较套路的判断必经边的做法是：将该边删除，重新跑费用流，如果答案发生改变，说明该边是必经边。

但如果我们直接枚举每条边删除再跑费用流，并不能再规定时间内跑完。经过观察我们发现，跑第一问的费用流时，一共只有n条男生到女生的边有流量。所以其他的男生到女生的边显然不可能为必经边。

所以我们只用枚举删除这n条有流量的边即可

最后贴代码

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define N 200
#define M 20005
using namespace std;
int n,m,s,t,h[N],tot=1,l[N][N],cutx,cuty;
struct edge{
    int to,nxt,cap,val;
}e[M<<1],ee[M<<1];
void add(int x,int y,int z,int cost){
    e[++tot].nxt=h[x];h[x]=tot;e[tot].to=y;e[tot].cap=z;e[tot].val=cost;ee[tot]=e[tot];
    e[++tot].nxt=h[y];h[y]=tot;e[tot].to=x;e[tot].cap=0;e[tot].val=-cost;ee[tot]=e[tot];
}
queue<int>q;
int v[N],d[N],pre[N],flow[N];
bool spfa(){
    memset(v,0,sizeof(v));
    memset(d,0xcf,sizeof(d));
    memset(pre,0,sizeof(pre));
    memset(flow,0,sizeof(flow));
    while(!q.empty())q.pop();
    q.push(s);v[s]=1;flow[s]=0x7fffffff;d[s]=0;
    while(!q.empty()){
        int x=q.front();q.pop();
        v[x]=0;
        for(int i=h[x];i;i=e[i].nxt)if(i^cutx&&i^cuty)if(e[i].cap&&d[x]+e[i].val>d[e[i].to]){
            d[e[i].to]=d[x]+e[i].val,flow[e[i].to]=min(flow[x],e[i].cap),pre[e[i].to]=i;
            if(!v[e[i].to])q.push(e[i].to),v[e[i].to]=1;
        }
    }
    //cout<<d[t]<<endl;
    if(d[t]^0xcfcfcfcf)return true;
    return false;
}
int sum,ans;
void updata(){
    int now=t;
    sum+=flow[now];
    ans+=flow[now]*d[now];
    while(now){
        e[pre[now]].cap-=flow[t];
        e[pre[now]^1].cap+=flow[t];
        now=e[pre[now]^1].to;
    }
}
signed main(){
    scanf("%d",&n);
    s=n+n+1;t=s+1;
    rep(i,1,n)rep(j,1,n){
        int x;scanf("%d",&x);
        add(i,n+j,1,x);
        l[i][j]=tot;
    }
    rep(i,1,n)add(s,i,1,0),add(n+i,t,1,0);
    while(spfa())updata();
    int last;
    printf("%d\n",last=ans);
    rep(i,1,n)rep(j,1,n)if(!e[l[i][j]].cap)l[i][j]=0;
    rep(i,1,n)rep(j,1,n){
        if(!l[i][j])continue;
        cutx=l[i][j];
        cuty=l[i][j]^1;
        sum=0;ans=0;
        rep(r,1,tot)e[r]=ee[r];
        while(spfa())updata();
        //cout<<i<<" "<<j<<" "<<l[i][j]<<" "<<sum<<" "<<ans<<endl;
        if(ans<last){printf("%d %d\n",i,j);break;}
    }
    return 0;
}