有n件工作要分配给n个人做。第i 个人做第j 件工作产生的效益为Cij 。试设计一个将 n件工作分配给n个人做的分配方案，使产生的总效益最大。
编程任务： 对于给定的n件工作和n个人，计算最优分配方案和最差分配方案。
把所有人看做二分图中顶点Xi，所有工作看做二分图中顶点Yi，建立附加源S汇T。
1、从S向每个Xi连一条容量为1，费用为0的有向边。
2、从每个Yi向T连一条容量为1，费用为0的有向边。3、从每个Xi向每个Yj连接一条容量为无穷大，费用为Cij的有向边。求最小费用最大流，最小费用流值就是最少运费，求最大费用最大流，最大费用流值就是最多运费。
/* * Problem: 线性规划与网络流24题 #18 分配问题 * Author: Guo Jiabao * Time: 2009.6.29 18:29 * State: Solved * Memo: 费用流*/#include#include #include #include #include using namespace std;const int MAXN=102*2,MAXM=MAXN*MAXN*2,INF=~0U>>1;struct Queue{ int Q[MAXN],head,tail,size; bool inq[MAXN]; void init() { memset(inq,0,sizeof(inq)); head = size =0; tail = -1; } void ins(int p) { size++; if (++tail == MAXN) tail = 0; Q[tail] = p; inq[p]=true; } int pop() { size--; int p=Q[head]; if (++head == MAXN) head = 0; inq[p]=false; return p; }}Q;struct edge{ edge *next,*op; int t,c,v;}*V[MAXN],ES[MAXM],*fe[MAXN];int N,S,T,EC,Ans,Costflow;int Sc[MAXN][MAXN],dist[MAXN],ft[MAXN];inline void addedge(int a,int b,int c,int v){ ES[++EC].next = V[a]; V[a]=ES+EC; V[a]->t=b; V[a]->c=c; V[a]->v=v; ES[++EC].next = V[b]; V[b]=ES+EC; V[b]->t=a; V[b]->c=0; V[b]->v=-v; V[a]->op = V[b]; V[b]->op = V[a];}void init(){ int i,j; freopen("job.in","r",stdin); freopen("job.out","w",stdout); scanf("%d",&N); S=0; T=N+N+1; for (i=1;i<=N;i++) for (j=1;j<=N;j++) scanf("%d",&Sc[i][j]);}bool SPFA(){ int i,j; for (i=S;i<=T;i++) dist[i]=INF; dist[S]=0; Q.ins(S); while (Q.size) { i=Q.pop(); for (edge *e=V[i];e;e=e->next) { j=e->t; if (e->c && dist[i] + e->v < dist[j]) { dist[j] = dist[i] + e->v; ft[j] = i; fe[j] = e; if (!Q.inq[j]) Q.ins(j); } } } return dist[T]!=INF;}void Augment(){ int i,delta=INF; for (i=T;i!=S;i=ft[i]) if (fe[i]->c < delta) delta = fe[i]->c; for (i=T;i!=S;i=ft[i]) { fe[i]->c -= delta; fe[i]->op->c += delta; Costflow += fe[i]->v * delta; }}void SPFAFlow(){ Q.init(); while (SPFA()) Augment();}void solve(){ int i,j; for (i=1;i<=N;i++) addedge(S,i,1,0); for (i=1;i<=N;i++) addedge(i+N,T,1,0); for (i=1;i<=N;i++) for (j=1;j<=N;j++) addedge(i,j+N,INF,Sc[i][j]); SPFAFlow(); printf("%d\n",Costflow); memset(V,0,sizeof(V)); EC=-1;Costflow=0; for (i=1;i<=N;i++) addedge(S,i,1,0); for (i=1;i<=N;i++) addedge(i+N,T,1,0); for (i=1;i<=N;i++) for (j=1;j<=N;j++) addedge(i,j+N,INF,-Sc[i][j]); SPFAFlow(); printf("%d\n",-Costflow);}int main(){ init(); solve(); return 0;}