[网络流24题]P4014 分配问题

题目描述

有 nn 件工作要分配给 n 个人做。第 i 个人做第 j 件工作产生的效益为 cij。试设计一个将 n 件工作分配给 n 个人做的分配方案，使产生的总效益最大。

题解：

第一反应裸的二分图最优匹配
最小总效益就是把边取负值求最大总效益即可
网络流也可以做，先将源点S与每个人连一条容量为1，费用为0的弧，同样从每一个任务向汇点连一条容量为1，费用为0的弧
然后对于每一个人和每一个任务，对应的从人向任务连一条容量为1，费用为Cij的弧，然后跑最大费用最大流和最小费用最大流就行了
为什么要标记容量为1，因为设置容量是为了防止一个点被多次匹配
代码都不是自己的，等日后有空补上

代码：

第一个方法：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<vector>
#include<ctime>

#define ll long long
#define R register
#define IL inline
#define Rf(a,b,c) for(R int (a)=(b);(a)<=(c);++(a))
#define Tf(a,b,c) for(R int (a)=(b);(a)>=(c);--(a))
#define MP make_pair
#define PA pair<int,int>
#define MES(a,b) memset((a),(b),sizeof((a)))
#define MEC(a,b) memset((a),(b),sizeof((b)))
#define D double

using namespace std;

const int N=505;

int n,m,lx[N],ly[N],link[N],w[N][N];
bool S[N],T[N];

IL int read() {
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=(ch-'0');ch=getchar();}
    return x*f;
}
IL void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

bool dfs(int x) {//这就是一般的二分图匹配
    S[x]=true;//把左边的点都加入S
    Rf(i,1,n) 
    if(lx[x]+ly[i]==w[x][i]&&!T[i]) {//判断这条边是否在相等子图里，不要再建图了
        T[i]=true;//右边的点加入T
        if(!link[i]||dfs(link[i])) {
            link[i]=x;
            return true;
        }
    }
    return false;
}

IL void update() {//n^2暴力找a，并修改
    R int a=1<<30;
    Rf(i,1,n) if(S[i]) 
        Rf(j,1,n) if(!T[j]) 
            a=min(a,lx[i]+ly[j]-w[i][j]); 
    Rf(i,1,n) {
        if(S[i]) lx[i]-=a;
        if(T[i]) ly[i]+=a;
    }
}

IL void KM() {
    Rf(i,1,n) {
        link[i]=lx[i]=ly[i]=0;
        Rf(j,1,n) lx[i]=max(lx[i],w[i][j]);//顶标初值
    }
    Rf(i,1,n) while(true) {
        Rf(j,1,n) S[j]=T[j]=false;//记得每次都要清空
        if(dfs(i)) break;//找到增广路了
        else update();//没找到就得松弛了
    }
} 


signed main()
{
    n=read();
    Rf(i,1,n) Rf(j,1,n) w[i][j]=read();
    KM();
    int sum1=0,sum2=0;
    Rf(i,1,n) sum1+=lx[i]+ly[i];//最后的顶标和就是最终答案了
    Rf(i,1,n) Rf(j,1,n) w[i][j]*=-1;//整体取负跑最小
    KM();
    Rf(i,1,n) sum2+=lx[i]+ly[i];
    write(-sum2);//记得要把答案再取负回来啊
    putchar('\n');write(sum1);

    return 0;
}

第二个方法：

#include<bits/stdc++.h>
#define FQ(i,a,b) for(register int i=a;i<=b;i++)
#define prf printf
#define scf scanf
#define ll long long
using namespace std;
const int N=5e4+10;
int INF,n,num=1,ne[N],fi[N],to[N],w[N],pl[N],S,T;
int dst[N],incf[N],P[N],vis[N],ans;
queue<int> q;
void FindMaxN()
{
    int fINDmAXn[1];
    memset(fINDmAXn,128/2,sizeof(fINDmAXn));    
    INF=fINDmAXn[0];
}
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;    
}
void add(int x,int y,int z,int kl)
{
    ne[++num]=fi[x];    
    fi[x]=num;    
    to[num]=y;   
    w[num]=z;
    pl[num]=kl; 
}
bool spfa()
{ 
    for(int i=S;i<=T;i++)dst[i]=INF; 
    memset(vis,0,sizeof(vis));  
    q.push(S),dst[S]=0;    
    incf[S]=1<<30,vis[S]=true;   
    while(!q.empty())
    {      
        int x=q.front();      
        vis[x]=false;q.pop();        
        for(int i=fi[x];i;i=ne[i])
        {            
            int ver=to[i];             
            if(dst[ver]>dst[x]+pl[i]&&w[i])
            {                
                dst[ver]=dst[x]+pl[i];                
                incf[ver]=min(incf[x],w[i]);                
                P[ver]=i;                
                if(!vis[ver])vis[ver]=true,q.push(ver);                 
            }             
        }    
    }
    return dst[T]!=INF;  
}
void update()
{    
    int x=T;     
    while(x!=S)
    {         
        int i=P[x];         
        w[i]-=incf[T];       
        w[i^1]+=incf[T];

        x=to[i^1];
    }
    ans+=dst[T]*incf[T];
}
bool spfa_d()
{
    for(int i=S;i<=T;i++)dst[i]=-INF;
    q.push(S),dst[S]=0;incf[S]=1<<30;
    while(!q.empty())
    {
        int x=q.front();
        vis[x]=false;q.pop();
        for(int i=fi[x];i;i=ne[i])
        {
            int ver=to[i];
            if(dst[ver]<dst[x]+pl[i]&&w[i])
            {
                dst[ver]=dst[x]+pl[i];
                incf[ver]=min(incf[x],w[i]);
                P[ver]=i;
                if(!vis[ver])vis[ver]=true,q.push(ver);
            }
        }
    }
    return dst[T]!=-INF;
}
void update_d()
{
    int x=T;
    while(x!=S)
    {
        int i=P[x];
        w[i]-=incf[T];
        w[i^1]+=incf[T];
        x=to[i^1];
    }
    ans+=dst[T]*incf[T];
}
void add_x(int x,int y,int z,int kl)
{
    add(x,y,z,kl);
    add(y,x,0,-kl);
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    FindMaxN();
    n=read();S=0,T=n*2+1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int x=read();
            add_x(i,j+n,1,x);
        }
    }
    for(int i=1;i<=n;i++)add_x(S,i,1,0),add_x(i+n,T,1,0);
    while(spfa())update();
    printf("%d\n",ans);
    ans=0;
    for(int i=2;i<=num;i+=2)w[i]+=w[i^1],w[i^1]=0;
    while(spfa_d())update_d();
    printf("%d\n",ans);
    return 0;        
}