洛谷3967 [TJOI2014]匹配

Luogu

BZOJ

分析

第一问

直接跑最大费用最大流即可。

第二问

枚举每一对,然后暴力重建,但是不要连这条边。

直接判断最大费用是否变小了即可。

一个优化:只要检查所有在第一问中满流了的边即可。(想一想,为什么?)

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=80+10;

int n,s,t,del;
int a[N][N],id[N][N<<1];
int ans[100010][2],top=0;

struct Edge { int v,w,c,nxt; } e[1000010];
int head[100010],cnt=2;

inline void addEdge(int u,int v,int w,int c) {
    id[u][v]=cnt;
    e[cnt]=(Edge){v,w,c,head[u]},head[u]=cnt++;
    e[cnt]=(Edge){u,0,-c,head[v]},head[v]=cnt++;
}

int dis[100010],inq[100010],lst[100010];

inline int spfa() {
    fill(dis+s,dis+t+1,-1e9),fill(lst+s,lst+t+1,0);
    queue<int> Q; Q.push(s); dis[s]=0,inq[s]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w,c=e[i].c;
            if (w&&dis[u]+c>dis[v]) {
                dis[v]=dis[u]+c,lst[v]=i;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return lst[t]!=0;
}

namespace backup { Edge e[1000010]; int id[N][N<<1]; }

int main() {
    n=read(),s=0,t=n+n+1;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j)
            a[i][j]=read();
    
    for (re int i=1;i<=n;++i) addEdge(s,i,1,0);
    for (re int i=1;i<=n;++i) addEdge(i+n,t,1,0);
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j)
            addEdge(i,j+n,1,a[i][j]);

    int mx=0;
    while (spfa()) {
        int f=2e9;
        for (re int i=lst[t];i;i=lst[e[i^1].v]) f=min(f,e[i].w);
        for (re int i=lst[t];i;i=lst[e[i^1].v]) e[i].w-=f,e[i^1].w+=f;
        mx+=dis[t]*f;
    }
    printf("%d\n",mx);

    memcpy(backup::e,e,sizeof(e)),memcpy(backup::id,id,sizeof(id));
    
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j) {
            if (backup::e[backup::id[i][j+n]].w) continue;
            
            //rebuild
            fill(head+s,head+t+1,0),cnt=2;
            for (re int k=1;k<=n;++k) addEdge(s,k,1,0);
            for (re int k=1;k<=n;++k) addEdge(k+n,t,1,0);
            for (re int k=1;k<=n;++k)
                for (re int l=1;l<=n;++l)
                    if (k!=i||l!=j) addEdge(k,l+n,1,a[k][l]);

            int now=0;
            while (spfa()) {
                int f=2e9;
                for (re int i=lst[t];i;i=lst[e[i^1].v]) f=min(f,e[i].w);
                for (re int i=lst[t];i;i=lst[e[i^1].v]) e[i].w-=f,e[i^1].w+=f;
                now+=dis[t]*f;
            }
            if (now<mx) ++top,ans[top][0]=i,ans[top][1]=j;
        }
    for (re int i=1;i<=top;++i) printf("%d %d\n",ans[i][0],ans[i][1]);
    
    return 0;
}
最后修改:2019 年 09 月 26 日 12 : 55 PM

发表评论