分配问题(费用流)

分配问题

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

题目描述

有

输入输出格式

输入格式：

文件的第

接下来的

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

5
14

说明

一个人只能修一个工件

把效率看成费用，因为一个人只能修一个工作，所以把容量设为1

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<queue>
  4 #include<cstring>
  5 using namespace std;
  6 
  7 const int INF=0x3f3f3f3f;
  8 const int N=50005;
  9 const int M=500005;
 10 int top;
 11 int dist[N],pre[N];
 12 bool vis[N];
 13 int c[N];
 14 int maxflow;
 15 
 16 struct Vertex{
 17     int first;
 18 }V[N];
 19 struct Edge{
 20     int v,next;
 21     int cap,flow,cost;
 22 }E[M];
 23 
 24 void init(){
 25     memset(V,-1,sizeof(V));
 26     top=0;
 27     maxflow=0;
 28 }
 29 
 30 void add_edge(int u,int v,int c,int cost){
 31     E[top].v=v;
 32     E[top].cap=c;
 33     E[top].flow=0;
 34     E[top].cost=cost;
 35     E[top].next=V[u].first;
 36     V[u].first=top++;
 37 }
 38 
 39 void add(int u,int v,int c,int cost){
 40     add_edge(u,v,c,cost);
 41     add_edge(v,u,0,-cost);
 42 }
 43 
 44 bool SPFA(int s,int t,int n){
 45     int i,u,v;
 46     queue<int>qu;
 47     memset(vis,false,sizeof(vis));
 48     memset(c,0,sizeof(c));
 49     memset(pre,-1,sizeof(pre));
 50     for(i=1;i<=n;i++){
 51         dist[i]=INF;
 52     }
 53     vis[s]=true;
 54     c[s]++;
 55     dist[s]=0;
 56     qu.push(s);
 57     while(!qu.empty()){
 58         u=qu.front();
 59         qu.pop();
 60         vis[u]=false;
 61         for(i=V[u].first;~i;i=E[i].next){
 62             v=E[i].v;
 63             if(E[i].cap>E[i].flow&&dist[v]>dist[u]+E[i].cost){
 64                 dist[v]=dist[u]+E[i].cost;
 65                 pre[v]=i;
 66                 if(!vis[v]){
 67                     c[v]++;
 68                     qu.push(v);
 69                     vis[v]=true;
 70                     if(c[v]>n){
 71                         return false;
 72                     }
 73                 }
 74             }
 75         }
 76     }
 77     if(dist[t]==INF){
 78         return false;
 79     }
 80     return true;
 81 }
 82 
 83 int MCMF(int s,int t,int n){
 84     int d;
 85     int i,mincost;
 86     mincost=0;
 87     while(SPFA(s,t,n)){
 88         d=INF;
 89         for(i=pre[t];~i;i=pre[E[i^1].v]){
 90             d=min(d,E[i].cap-E[i].flow);
 91         }
 92         maxflow+=d;
 93         for(i=pre[t];~i;i=pre[E[i^1].v]){
 94             E[i].flow+=d;
 95             E[i^1].flow-=d;
 96         }
 97         mincost+=dist[t]*d;
 98     }
 99     return mincost;
100 }
101 
102 int aa[105][105];
103 
104 int main(){
105     int n,m;
106     int v,u,w,c;
107     int s,t;
108     cin>>n;
109     init();
110 
111     for(int i=1;i<=n;i++){
112         for(int j=1;j<=n;j++){
113             cin>>aa[i][j];
114             add(i,n+j,1,aa[i][j]);
115         }
116     }
117     s=0,t=n+n+1;
118     for(int i=1;i<=n;i++){
119         add(s,i,1,0);
120         add(n+i,t,1,0);
121     }
122     int ans=MCMF(s,t,n+n+2);
123     cout<<ans<<endl;
124     init();
125     for(int i=1;i<=n;i++){
126         for(int j=1;j<=n;j++){
127             add(i,n+j,1,-aa[i][j]);
128         }
129     }
130     s=0,t=n+n+1;
131     for(int i=1;i<=n;i++){
132         add(s,i,1,0);
133         add(n+i,t,1,0);
134     }
135     ans=MCMF(s,t,n+n+2);
136     cout<<-ans<<endl;
137 }

View Code