题解：AT_abc231_h [ABC231H] Minimum Coloring

· · 题解

Solution

最小费用上下界可行流！

先建立最基础的网络流模型：建立二分图。左部点表示行，右部点表示列。在 X_{a_i} 和 Y_{b_i} 连上 c_i 的边。

建立超级源点 s，和左部点所有点连上下界为 1 的边。同理建立超级汇点。

求这张网络的最小费用可行流即可。复杂度理论上是 O(n^3)（认为 h、w、n 同阶），但是网络长的太规律了所以跑得很快，很快！

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXV=2000+10,MAXE=MAXV*100;
int h,w,e,s,t,mc,mf,tmp,tot=1,ev,deg[MAXV],hd[MAXV],cur[MAXV],dis[MAXV],vis[MAXV];
struct Edge {int to,nxt,f,c;}edge[MAXE];
void add_edge(int u,int v,int f,int c) {return edge[++tot]={v,hd[u],f,c},hd[u]=tot,edge[++tot]={u,hd[v],0,-c},hd[v]=tot,void();}
int spfa(int s,int t) {
    ffor(i,0,t) dis[i]=0x3f3f3f3f3f3f3f3f,vis[i]=0,cur[i]=hd[i];
    queue<int> q;
    dis[s]=0,q.push(s);
    while(!q.empty()) {
        int u=q.front();
        vis[u]=0,q.pop();
        for(int i=hd[u];i;i=edge[i].nxt) {
            int to=edge[i].to,f=edge[i].f,c=edge[i].c;
            if(!f||dis[to]<=dis[u]+c) continue ;
            dis[to]=dis[u]+c;
            if(!vis[to]) vis[to]=1,q.push(to);
        }
    }
    return dis[t]!=0x3f3f3f3f3f3f3f3f;
}
int dinic(int u,int mx) {
    if(u==t) return mx;
    int res=0;
    vis[u]=1;
    for(int i=cur[u];i;i=edge[i].nxt) {
        int to=edge[i].to,f=edge[i].f,c=edge[i].c; cur[u]=i;
        if(dis[to]!=dis[u]+c||vis[to]||!f) continue ;
        int tmp=dinic(to,min(mx,f));
        if(tmp) {
            res+=tmp,mx-=tmp,mc+=c*tmp,edge[i].f-=tmp,edge[i^1].f+=tmp;
            if(!mx) break;
        }
        else dis[to]=0x3f3f3f3f3f3f3f3f;
    }
    return vis[u]=0,res;
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>h>>w>>e,s=h+w+2,t=h+w+3;
    add_edge(h+w+1,0,10000,0);
    ffor(i,1,h) deg[0]++,deg[i]--,add_edge(0,i,10000,0);
    ffor(i,h+1,h+w) deg[i]++,deg[h+w+1]--,add_edge(i,h+w+1,10000,0);
    ffor(i,1,e) {
        int x,y,c;
        cin>>x>>y>>c;   
        add_edge(x,y+h,1,c);
    }
    ffor(i,0,h+w+1) if(deg[i]>0) add_edge(i,t,deg[i],0);
    else add_edge(s,i,-deg[i],0);
    while(spfa(s,t)) while(dinic(s,10000));
    cout<<mc;
    return 0;
}