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



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