P3967 [TJOI2014]匹配 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • jiangly
    只用枚举你跑出来的完美匹配中的 n 条边啊,复杂度才是对的
作者: Khassar 更新时间: 2018-03-07 15:25  在Ta的博客查看 举报    4  

我觉得费用流的那篇题解已经把题意说清楚了,所以我就特来贡献一下二分图最佳完美匹配的KM写法。

具体理论一些的东西你们可以去看我在$P4014$写的题解,里面说的比较多这里就不在写了。

要特别注意的是虽然我用的是$n^3$优化过的KM(我那篇题解里用的是$n^4$的,我会在代码里用注释简单说一下$n^3$优化,其实就是加了个松弛量slack),但还是在加上$n^2$枚举删边后华丽丽地TLE了3个点。
所以需要在枚举时判一下这条边有没有可能成为答案(具体看代码吧)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<ctime>

#define ll long long
#define R register
#define IL inline
#define Rf(a,b,c) for(R int (a)=(b);(a)<=(c);++(a))
#define Tf(a,b,c) for(R int (a)=(b);(a)>=(c);--(a))
#define MP make_pair
#define PA pair<int,int>
#define MES(a,b) memset((a),(b),sizeof((a)))
#define MEC(a,b) memcpy((a),(b),sizeof((b)))
#define D double

using namespace std;

const int N=105;

int n,m,lx[N],ly[N],link[N],w[N][N],sl[N],sum,Ans,Link[N];
bool S[N],T[N];

IL int read() {
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=(ch-'0');ch=getchar();}
    return x*f;
}
IL void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

bool dfs(int x) {//二分图匹配过程
    S[x]=true;
    Rf(i,1,n) 
        if(lx[x]+ly[i]==w[x][i]) {
            if(!T[i]) {
                T[i]=true;
                if(!link[i]||dfs(link[i])) {
                    link[i]=x;
                    return true;
                }
            }
        }
        else {//用不能进入相等子图的边更新一下松弛量sl
            sl[i]=min(sl[i],lx[x]+ly[i]-w[x][i]);
        }
    return false;
}

IL void update() {
    R int a=1e9;
    Rf(j,1,n) if(!T[j]) //在松弛量中找,而不是再n^2枚举,优化在此
        a=min(a,sl[j]); 
    Rf(i,1,n) {
        if(S[i]) lx[i]-=a;
        if(T[i]) ly[i]+=a;
        sl[i]-=a;
    }
}

IL void KM() {
    Rf(i,1,n) {
        link[i]=lx[i]=ly[i]=0;
        Rf(j,1,n) lx[i]=max(lx[i],w[i][j]);
    }
    Rf(i,1,n) while(true) {
        Rf(j,1,n) {
            S[j]=T[j]=false;sl[j]=1e9;
        }
        if(dfs(i)) break;
        else update();
    }
} 

signed main()
{
    n=read();
    Rf(i,1,n) Rf(j,1,n) w[i][j]=read();
    KM();
    Rf(i,1,n) sum+=lx[i]+ly[i];
    write(sum);putchar('\n');
    Ans=sum;MEC(Link,link);//先记录一个最佳完美匹配
    Rf(k,1,n) Rf(j,1,n) {//枚举删边
        if(w[k][j]<w[Link[j]][j]) continue;
   //如果这条边比j在一个最佳完美匹配中匹配的边的边权要小,那么这条边一定不会在任意一个最佳完美匹配中,就没必要尝试删它。
        R int tmp=w[k][j];
        w[k][j]=-1e7;
        sum=0;
        KM();
        Rf(i,1,n) sum+=lx[i]+ly[i];
        w[k][j]=tmp;
        if(sum!=Ans) {
            printf("%d %d\n",k,j);
        }
    }

    return 0;
}

啦啦啦,KM跑得飞快

评论

  • Venus
    码风好评
  • HellPix
    原来zkw可以加弧优化啊
  • three_trees
    超时怎么处理
  • three_trees
    解决了%
作者: 雨季 更新时间: 2018-03-04 21:11  在Ta的博客查看 举报    4  

题解

题意很明确

第一问

$\quad \ \ $求带权二分图的最佳完美匹配,然而并不会写带权匹配╮(╯▽╰)╭,于是写了最大费用最大流。
建图:$\ \ \ \ $超级源 $\ \ \ \ \ \to \ \ \ \ \ $ 男生$(i)$ $\qquad\ $容量为1,费用为0
$\ \ \ \ $ $\qquad\ $男生$(i)$ $ \ \ \ \ \to\ $ 女生$(j+n)\ $容量为1,费用为幸福值
$\quad\ \ \ \ $女生$(j+n)$$$\ \ \ \to\ \ \ \ \ $超级汇$\qquad\ \ \ \ $容量为1,费用为0

第二问

$\quad \ \ $求出所有完美匹配中都有的边
$\quad \ \ $通过第一问,我们知道了一个完美匹配的方案,以及完美匹配下的最大幸福值。
$\quad \ \ $那么我们可以枚举这个完美匹配中的每一条边,将它删掉,再次跑完美匹配,如果这次的最大费用比没有删掉它之前的答案小了,那么说明这条边一定在完美匹配中
注:如果写费用流的话,删边时记的将这条边对应的反向边一起删掉,不然的话你大概会死循环。。。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define N 500

int n,S,T;
bool in[N][N];
bool check[N*N];

inline int read() {
    int tmp=0,w=1;
    char ch=0;
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) tmp=(tmp<<1)+(tmp<<3)+ch-'0',ch=getchar();
    return tmp*w;
}

struct node {
    int u,v,c,f,nex;
}e[N*N],ee[N*N];
int tot=1,h[N],use[N];
void add(int u,int v,int c,int f) {
    e[++tot].u=u,e[tot].v=v,e[tot].c=c,e[tot].f= f,e[tot].nex=h[u],h[u]=tot;
    e[++tot].u=v,e[tot].v=u,e[tot].c=0,e[tot].f=-f,e[tot].nex=h[v],h[v]=tot;
}

int dis[N];
bool vis[N];
bool donot[N*N];
deque<int>q;
bool spfa() {
    for(int i=S;i<=T;++i) dis[i]=-1e9,vis[i]=0;
    q.push_back(T);
    dis[T]=0;
    int x,xx;
    while(!q.empty()) {
        x=q.front();
        q.pop_front();
        vis[x]=0;
        for(int i=h[x];i;i=e[i].nex) {
            xx=e[i].v;
            if(donot[i]) continue;
            if(e[i^1].c&&dis[xx]<dis[x]-e[i].f) {
                dis[xx]=dis[x]-e[i].f;
                if(!vis[xx]) {
                    vis[xx]=1;
                    if(q.empty()||dis[xx]<dis[q.front()]) q.push_back(xx);
                    else q.push_front(xx);
                }
            }
        }
    }
    return dis[S]>-1e9;
}
bool mark[N];
int dfs(int x,int want) {
    mark[x]=1;
    if(x==T||!want) return want;
    int f=0,get=0,xx=0;
    for(int i=use[x];i;i=e[i].nex) {
        if(donot[i]) continue;
        xx=e[i].v;
        if(e[i].c&&!mark[xx]&&dis[xx]==dis[x]-e[i].f) {
            f=dfs(xx,min(want,e[i].c));
            if(!f) continue;
            e[i].c-=f;
            e[i^1].c+=f;
            get+=f;
            want-=f;
            use[x]=i;
            if(!want) break;
        }
    }
    return get;
}

int mfmc() {
    int res=0;
    while(spfa()) {
        mark[T]=1;
        while(mark[T]) {
            for(int i=S;i<=T;++i) use[i]=h[i],mark[i]=0;
            res+=dis[S]*dfs(S,1e9);
        }
    }
    return res;
}

int main()
{
    scanf("%d",&n);
    S=0,T=n+n+1;
    int x;
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=n;++j) {
            x=read();
            add(i,j+n,1,x);
        } 
    }
    int cut=tot;
    for(int i=1;i<=n;++i) add(S,i,1,0),add(i+n,T,1,0);
    memcpy(ee,e,sizeof(e));
    int ans=mfmc();
    for(int i=2;i<=cut;i+=2) if(!e[i].c) check[i]=1;
    printf("%d\n",ans);
    for(int i=2;i<=cut;i+=2) {
        if(check[i]) {
            donot[i]=1,donot[i^1]=1;
            memcpy(e,ee,sizeof(ee));    
            x=mfmc();
            if(x<ans) in[e[i].u][e[i].v]=1;
            donot[i]=0,donot[i^1]=0;
        }
    }
    for(int i=1;i<=n;++i) {
        for(int j=1;j<=n;++j) {
            if(in[i][j+n]) printf("%d %d\n",i,j);
        }
    }
    return 0;
}

评论

  • 龙翔凤翥
    orz 我太强了,tql,akioi
  • 龙翔凤翥
    这种ioi题目我都能轻松切掉,写出题解
  • 龙翔凤翥
    哎,都没人来%我
  • 龙翔凤翥
    被机惨了,抱歉
作者: 龙翔凤翥 更新时间: 2019-09-24 20:15  在Ta的博客查看 举报    0  

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;
    }
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。