KM算法模板

P3967 [TJOI2014]匹配
时间复杂度是n3

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
#define fi first
#define se second
const int M=105;

int n;
int w[M][M];
int match[M],slack[M];
int lx[M],ly[M];
bool vis1[M],vis2[M];
int ans;
pii a[M];

bool dfs(int now) {
    vis1[now]=1;
    for(int i=1;i<=n;i++) {
        int cnt=lx[now]+ly[i]-w[now][i];
        if(cnt==0&&vis2[i]==0) {
            vis2[i]=1;
            if(match[i]==0||dfs(match[i])) {
                match[i]=now;
                return 1;
            }
        }
        else slack[i]=min(slack[i],cnt);
    }
    return 0;
}

void update() {
    int a=0x3f3f3f3f;
    for(int i=1; i<=n; i++) {
        if(!vis2[i])
            a=min(a,slack[i]);
    }
    for(int i=1; i<=n; i++) {
        if(vis1[i])lx[i]-=a;
        if(vis2[i])ly[i]+=a;
    }
 
}

int km() {
    memset(lx,0,sizeof(lx));
    memset(ly,0,sizeof(ly));
    memset(match,0,sizeof(match));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            lx[i]=max(lx[i],w[i][j]);
    //for(int i=1;i<=n;i++)cout<<lx[i]<<' ';cout<<endl;
    for(int i=1;i<=n;i++) {
        memset(slack,0x3f,sizeof(slack));
        while(1) {
            memset(vis1,0,sizeof(vis1));
            memset(vis2,0,sizeof(vis2));
            if(dfs(i))break;
            update();
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
        if(match[i])sum+=w[match[i]][i];
    return sum;
}

bool check(int x,int y) {
    int tmp=w[x][y];
    w[x][y]=-1e8;
    int sum=km();
    w[x][y]=tmp;
    return sum!=ans;
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        cin>>w[i][j];
    ans=km();
    cout<<ans<<endl;
    for(int i=1;i<=n;i++)
        a[i]={match[i],i};
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
        if(check(a[i].fi,a[i].se))cout<<a[i].fi<<' '<<a[i].se<<'\n';
    return 0;
}