P4014 分配问题

思路：费用流

提交：(1)次

题解：

源点向人连流量为(1)费用为(0)的边，人向每个工作连流量为(1)费用为(c_{i,j})的边，每个工作向汇点连流量为(1)费用为(0)的边。
跑最小费用最大流。至于最大费用把费用全部取个负数输出答案时再取个负数就好。

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define R register int
using namespace std;
namespace Luitaryi {
template<class I> inline I g(I& x) { x=0;
  register I f=1; register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
  do x=x*10+(ch-48); while(isdigit(ch=getchar())); return x*=f;
} const int N=210,M=10010,Inf=0x3f3f3f3f;
int n,m,s,t,ans,cnt=1,a[110][110];
int vr[M<<1],nxt[M<<1],w[M<<1],c[M<<1],fir[N],d[N]; bool vis[N];
inline void clear() {
  memset(nxt,0,sizeof(nxt)),memset(fir,0,sizeof(fir)); cnt=1; ans=0;
}
inline void add(int u,int v,int ww,int cc) {vr[++cnt]=v,nxt[cnt]=fir[u],w[cnt]=ww,c[cnt]=cc,fir[u]=cnt;}
inline bool spfa() { memset(d,0x3f,sizeof(d)),memset(vis,0,sizeof(vis));
  queue<int> q; vis[s]=true,d[s]=0,q.push(s);
  while(!q.empty()) { R u=q.front(); q.pop(); vis[u]=false;
    for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
      if(w[i]&&d[v]>d[u]+c[i]) {
        d[v]=d[u]+c[i];
        if(!vis[v]) vis[v]=true,q.push(v);
      }
    }
  } return d[t]<Inf;
}
inline int dfs(int u,int f) {
  if(u==t||f<=0) return f; R res=f; vis[u]=true;
  for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
    if(w[i]&&d[v]==d[u]+c[i]&&!vis[v]) {
      R tmp=dfs(v,min(res,w[i]));
      res-=tmp,w[i]-=tmp,w[i^1]+=tmp;
      if(!res) break;
    }
  } return f-res;
}
inline void dinic() {R tmp; while(spfa()) while(tmp=dfs(s,Inf),tmp!=0) memset(vis,0,sizeof(vis)),ans+=tmp*d[t];}
inline void main() { g(n),s=2*n+1,t=2*n+2; 
  for(R i=1;i<=n;++i) for(R j=1,x;j<=n;++j) a[i][j]=g(x),add(i,j+n,1,x),add(j+n,i,0,-x);
  for(R i=1;i<=n;++i) add(s,i,1,0),add(i,s,0,0),add(i+n,t,1,0),add(t,i+n,0,0); dinic(); printf("%d
",ans); clear(); 
  for(R i=1;i<=n;++i) for(R j=1,x;j<=n;++j) x=a[i][j],add(i,j+n,1,-x),add(j+n,i,0,x);
  for(R i=1;i<=n;++i) add(s,i,1,0),add(i,s,0,0),add(i+n,t,1,0),add(t,i+n,0,0); dinic(); printf("%d
",-ans);
}
} signed main() {Luitaryi::main(); return 0;}

2019.08.19
81