(TIOJ) 1042 . E.老問題 [各種KM]

http://tioj.infor.org/problems/1042

二分圖最大權匹配算法大集合(?)

法一：Min-Cost Max-Flow

#include <iostream>
#include <stdio.h>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
using namespace std;

typedef pair<int,int> pii;

struct CostFlow {
    int n,s,t;
    static const int MAX_N = 206;
    struct Edge {
        int to,cap,rev,cost;
    };
    vector<Edge> edg[MAX_N];
    void init(int _n,int _s,int _t) {
        n=_n;
        s=_s;
        t=_t;
        for (int i=0;n>=i;i++) {
            edg[i].clear();
        }
    }
    #define SZ(x) ((int)(x).size())
    void add_edge(int from,int to,int cap,int cost) {
        edg[from].push_back({to,cap,SZ(edg[to]),cost});
        edg[to].push_back({from,0,SZ(edg[from])-1,-cost});
    }
    const int INF = 1e9 +7;
    int dis[MAX_N],pre[MAX_N],pre_id[MAX_N];
    bool in_que[MAX_N];
    pii flow() {
        int cost=0,flow=0;
        while (true) {
            for (int i=0;n>=i;i++) {
                dis[i] = INF;
                in_que[i] = 0;
            }
            queue<int> que;
            que.push(s);
            dis[s] = 0;
            while (!que.empty()) {
                int t=que.front();
                que.pop();
                in_que[t] = false;
                int id=0;
                for (Edge e:edg[t]) {
                    if (e.cap >0 && dis[e.to] > dis[t] + e.cost) {
                        dis[e.to] = dis[t] + e.cost;
                        pre[e.to] = t;
                        pre_id[e.to] = id;
                        if (!in_que[e.to]) {
                            in_que[e.to]=1;
                            que.push(e.to);
                        }
                    }
                    id++;
                }
            }
            if (dis[t] == INF) break;
            if (dis[t] > 0) break;
            int mn_flow = INF;
            for (int i=t;i!=s;i=pre[i]) {
                mn_flow = min(mn_flow,edg[pre[i]][pre_id[i]].cap);
            }
            flow += mn_flow;
            cost += mn_flow * dis[t];
            for (int i=t;i!=s;i=pre[i]) {
                edg[pre[i]][pre_id[i]].cap -= mn_flow;
                edg[i][edg[pre[i]][pre_id[i]].rev].cap += mn_flow;
            }
        }
        return make_pair(flow,cost);
    }
} flow;

const int MAX_N = 1e2 + 6;

int a[MAX_N][MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        if (!n) break;
        flow.init(2*n+2,0,2*n+1);
        for (int i=1;n>=i;i++) {
            for (int j=1;n>=j;j++) {
                scanf("%d",&a[i][j]);
                flow.add_edge(i,j+n,1,-a[i][j]);
            }
        }
        for (int i=1;n>=i;i++) {
            flow.add_edge(0,i,1,0);
        }
        for (int j=1;n>=j;j++) {
            flow.add_edge(j+n,2*n+1,1,0);
        }
        pii ret=flow.flow();
        printf("%d\n",-ret.second);
    }
}

法二：KM O(n^4)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;

#define LL   long long
#define ld   long double
#define pii  pair<int,int>
#define pLL  pair<LL,LL>
#define vint vector<int>
#define vLL  vector<LL>
#define vpii vector<pii>

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e));
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e),(f));

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

int myRnd() {
    return abs(  ((rand()<<15) | rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)|rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 100 + 6;

LL a[N][N];

const LL INF = 1e15 + 7;

bool vx[N],vy[N];
LL Lx[N],Ly[N];
int match[N];

int n;

bool dfs(int i)
{
    vx[i] = 1;
    REP1(j,n)
    {
        if (!vy[j])
        {
            if (Lx[i] + Ly[j] == a[i][j])
            {
                vy[j] = 1;
                if (match[j] == -1 || dfs(match[j]))
                {
                    match[j] = i;
                    return true;
                }
            }
        }
    }
    return false;
}

int main () {
    srand(time(NULL));
    while (scanf("%d",&n) != EOF)
    {
        if (n==0) break;
        REP1(i,n)
        {
            REP1(j,n)
            {
                SL(a[i][j]);
                a[i][j] = max(a[i][j],0LL);
            }
        }
        MEM0(Lx);
        MEM0(Ly);
        REP1(i,n)
        {
            REP1(j,n)
            {
                Lx[i] = max(Lx[i],a[i][j]);
            }
        }
        MEM1(match);
        //Parr(Lx,1,n);
        //Parr(Ly,1,n);
        REP1(i,n)
        {
            //cout<<"I = "<<i<<endl;
            while (true)
            {
                MEM0(vx);
                MEM0(vy);
                if (dfs(i)) break;
                else
                {
                    LL mn = INF;
                    REP1(i,n)
                    {
                        if (!vx[i]) continue;
                        REP1(j,n)
                        {
                            if (vy[j]) continue;
                            mn = min(mn , Lx[i] + Ly[j] - a[i][j]);
                        }
                    }
                    if (mn < 0) break;
                    REP1(i,n)
                    {
                        if (vx[i]) Lx[i] -= mn;
                        if (vy[i]) Ly[i] += mn;
                    }
                }
            }
        }
        LL ans=0;
        //bool check=true;
        REP1(i,n)
        {
            if (a[ match[i] ][i] >= 0)
            {
                ans += a[ match[i] ][i];
            }
        }
        if (ans < 0) ans = 0;
        PL(ans);
    }
}

法三：KM O(n^3)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cassert>
using namespace std;

#define LL   long long
#define ld   long double
#define pii  pair<int,int>
#define pLL  pair<LL,LL>
#define vint vector<int>
#define vLL  vector<LL>
#define vpii vector<pii>

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e));
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a),(b),(c),(d),(e),(f));

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

int myRnd() {
    return abs(  ((rand()<<15) | rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)|rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 100 + 6;

LL a[N][N];

const LL INF = 1e15 + 7;

bool vx[N],vy[N];
LL Lx[N],Ly[N];
int match[N];

int n;

LL slack_y[N];

bool dfs(int i,bool change = true)
{
    if (vx[i]) return false;
    vx[i] = 1;
    REP1(j,n)
    {
        LL val = Lx[i] + Ly[j] - a[i][j];
        if (!vy[j])
        {
            if (Lx[i] + Ly[j] == a[i][j])
            {
                vy[j] = 1;
                if (match[j] == -1 || dfs(match[j],change))
                {
                    if (change)match[j] = i;
                    return true;
                }
            }
            else
            {
                slack_y[j] = min(slack_y[j],val);
            }
        }
    }
    return false;
}

int main () {
    srand(time(NULL));
    while (scanf("%d",&n) != EOF)
    {
        if (n==0) break;
        REP1(i,n)
        {
            REP1(j,n)
            {
                SL(a[i][j]);
                a[i][j] = max(a[i][j],0LL);
            }
        }
        MEM0(Lx);
        MEM0(Ly);
        REP1(i,n)
        {
            REP1(j,n)
            {
                Lx[i] = max(Lx[i],a[i][j]);
            }
        }
        MEM1(match);
        //Parr(Lx,1,n);
        //Parr(Ly,1,n);
        REP1(i,n)
        {
            //cout<<"I = "<<i<<endl;
            REP1(i,n) slack_y[i] = INF;
            MEM0(vx);
            MEM0(vy);
            if (dfs(i)) continue;
            bool flag = true;
            while (flag)
            {
                LL mn = INF;
                REP1(j,n)
                {
                    if (!vy[j]) mn = min(mn,slack_y[j]);
                }
                REP1(i,n)
                {
                    if (vx[i]) Lx[i] -= mn;
                    if (vy[i]) Ly[i] += mn;
                    else slack_y[i] -= mn;
                }
                REP1(j,n)
                {
                    if (!vy[j] && slack_y[j] == 0)
                    {
                        vy[j] = 1;
                        if (match[j] == -1 || dfs(match[j],false))
                        {
                            flag = false;
                            break;
                        }
                    }
                }
            }
            MEM0(vx);
            MEM0(vy);
            assert(dfs(i));
        }
        LL ans=0;
        //bool check=true;
        REP1(i,n)
        {
            if (a[ match[i] ][i] >= 0)
            {
                ans += a[ match[i] ][i];
            }
        }
        if (ans < 0) ans = 0;
        PL(ans);
    }
}