https://www.luogu.org/problemnew/show/P4014

最小费用最大流

最大费用最小流

#include 
     
      using namespace std;const int maxn = 300;const int inf = 0x3f3f3f3f;int n,m;int ck(int x){    return x;}int ls(int x){    return m+x;}int head[maxn];int tot =0;struct edge{    int v,nex,w,c;}e[maxn*maxn];void addedge(int u,int v,int w,int c){    e[tot] = (edge){v,head[u],w,c};    head[u] = tot++;    e[tot] = (edge){u,head[v],0,-c};    head[v] = tot++;}int vis[maxn];int dis[maxn];int pre[maxn];bool spfa(int S,int T){    memset(dis,0x3f,sizeof(dis));    memset(vis,0,sizeof(vis));    queue
      
        q;    vis[S] = 1;    q.push(S);    dis[S] = 0;    while(!q.empty()){        int now = q.front();        q.pop();        vis[now] = 0;        for(int i=head[now];i!=-1;i=e[i].nex){            int w = e[i].w;            int c = e[i].c;            int v = e[i].v;            if(w>0 && dis[v]>dis[now]+c){                dis[v] = dis[now]+c;                pre[v] = i;                if(vis[v]==0){                    vis[v] = 1;                    q.push(v);                }            }        }    }    return dis[T]==0x3f3f3f3f?false:true;}int ed(int S,int T,int &maxflow){    int ret = 0;    int flow = 0x3f3f3f3f;    int p;    for(int i=T;i!=S;i=e[p^1].v){        p = pre[i];        flow = min(flow,e[p].w);    }    for(int i=T;i!=S;i=e[p^1].v){        p = pre[i];        ret+=flow*e[p].c;        e[p].w-=flow;        e[p^1].w+=flow;    }    maxflow+=flow;    return ret;}void solve(int S,int T,int k){    int maxflow = 0;    int ans = 0;    while(spfa(S,T)){        ans+=ed(S,T,maxflow);    }    printf("%d\n",ans*k);}int aa[maxn],bb[maxn],cc[maxn][maxn];void solve2(int S,int T){    memset(head,-1,sizeof(head));    tot = 0;    for(int i=1;i<=m;i++){        addedge(S,ck(i),1,0);    }    for(int i=1;i<=n;i++){        addedge(ls(i),T,1,0);    }    for(int i=1;i<=m;i++){        for(int j=1;j<=n;j++){            addedge(ck(i),ls(j),1,-cc[i][j]);        }    }    solve(S,T,-1);}int main(){    memset(head,-1,sizeof(head));    scanf("%d",&m);    n=m;    int S = 0;    int T = m+n+1;    for(int i=1;i<=m;i++){        addedge(S,ck(i),1,0);    }    for(int i=1;i<=n;i++){        int t;        addedge(ls(i),T,1,0);    }    for(int i=1;i<=m;i++){        for(int j=1;j<=n;j++){            int t;            scanf("%d",&t);            cc[i][j] = t;            addedge(ck(i),ls(j),1,t);        }    }    solve(S,T,1);    solve2(S,T);    return 0;}