分配问题

题目描述

有 $c_{ij}cij 。试设计一个将 nn 件工作分配给 nn 个人做的分配方案，使产生的总效益最大。$

输入输出格式

输入格式：

文件的第

接下来的 $c_{ij}cij ，表示第 ii 个人做第 jj 件工作产生的效益为 c_{ij}cij 。$

输出格式：

两行分别输出最小总效益和最大总效益。

输入输出样例

输入样例#1：

52 2 2 1 22 3 1 2 42 0 1 1 12 3 4 3 33 2 1 2 1

输出样例#1：

说明

一个人只能修一个工件

2018.7.5测试T3

当时打出了最小费用，却没敢做，打了10分的搜索暴力(；′⌒`)

其实挺简单的

二分图，左边是人，右边的工作，

建立一个超级源点，一个超级汇点

建的边流量都是1（一个人只能修一个工件）

与源点或汇点相连的费用全是0

人与工作之间的费用是他们之间的效益

一个最大一个最小，取反一下就可以辣

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define inf 0x3f3f3f3f 6 using namespace std; 7  8 int n,s,t; 9 int a[101][101];10 struct node{11     int u,v,flow,spend,next;12 }e[100100];13 int head[100100],tot=1;14 int from[100100],vis[100100],dis[100100];15 int ans;16 17 void add_node(int a,int b,int f,int s) {18     e[++tot]=(node){a,b,f,s,head[a]};19     head[a]=tot;20 }21 bool SPFA() {22     memset(dis,inf,sizeof(dis));23     memset(vis,0,sizeof(vis));24     queue
         
           q;25     q.push(s);26     dis[s]=0;27     while(!q.empty()) {28         int x=q.front();29         q.pop();vis[x]=0;30         for(int i=head[x];i;i=e[i].next) {31             int v=e[i].v;32             int u=e[i].u;33             int f=e[i].flow;34             int s=e[i].spend;35             if(dis[u]+s < dis[v]&& f>0) {36                 dis[v]=dis[u]+s;37                 from[v]=i;38                 if(!vis[v]) {39                     vis[v]=1;40                     q.push(v);41                 }42             }43         }44     }45     return dis[t]!=inf;46     47 }48 void work() {49     int mn=inf;50     for(int i=t;i!=s;i=e[from[i]].u)51         mn=min(mn,e[from[i]].flow);52     for(int i=t;i!=s;i=e[from[i]].u) {53         e[from[i]].flow-=mn;54         e[from[i]^1].flow+=mn; 55         ans+=mn*e[from[i]].spend;56     }57 }58 59 int main()60 {61     scanf("%d",&n);62        //1到n代表人63        //n+1到n+n代表工作64        //0代表超级源点65        //n+n+1代表超级汇点66     for(int i=1;i<=n;++i)67         for(int j=1;j<=n;++j)68             scanf("%d",&a[i][j]),add_node(i,j+n,1,a[i][j]),add_node(j+n,i,0,-a[i][j]);69     s=0,t=n+n+1;70     for(int i=1;i<=n;++i)add_node(s,i,1,0),add_node(i,s,0,0),add_node(n+i,t,1,0),add_node(t,n+i,0,0);71 72         //建边后直接套板子73     while(SPFA()) work();74     printf("%d\n",ans);75     76     //清空再来一遍， 存一遍的骚操作蒟蒻表示掌握不来╮(╯▽╰)╭77     memset(e,0,sizeof(e));78     memset(head,0,sizeof(head));79     memset(from,0,sizeof(from));80     memset(vis,0,sizeof(vis));81     memset(dis,0,sizeof(dis));82     ans=0;tot=1;83     84         //基本就是上面在复制一遍85     for(int i=1;i<=n;++i)86         for(int j=1;j<=n;++j)87             add_node(i,j+n,1,-a[i][j]),add_node(j+n,i,0,a[i][j]);88     s=0,t=n+n+1;89     for(int i=1;i<=n;++i)add_node(s,i,1,0),add_node(i,s,0,0),add_node(n+i,t,1,0),add_node(t,n+i,0,0);90     while(SPFA()) work();91     printf("%d",-ans);92     return 0;93 }