网络流24题——餐巾计划问题(有源汇的最小费用可行流)

链接：https://www.oj.swust.edu.cn/oj/problem/show/1745

分析：

我的想法是，首先每天的餐巾数有限制，所以先拆点，从Xi向Yi连一条容量和下界均为ri的边，Xi看作每天得到的新餐巾（洗好的+新买的），从s向Xi连一条容量为inf，费用为p的边；再从Xi向X(i+m)连一条容量为inf，费用为f的边，向X(i+n)连容量为inf，费用为s的边，还有不洗的那些，直接留到下一天，就是从Xi到X(i+1)连一条容量为inf，费用为0的边(最后一天的直接连到t上)，然后求这个图的最小费用可行流。

带下界的最小费用可行流求法：先从t到s连容量为inf，费用为0的边，变成无源无汇的图，增加附加源汇S、T，然后对于每一条从u到v下界为b上界为c费用为w的边，拆成u到T容量为b、费用为w的边和S到v容量为b费用为0的边，再把u到v的边容量改为c-b，求S-T最小费用最大流即为所求，当且仅当附加边均满流时问题有解。

题解是二分图。。比我的做法简单。。

我的做法：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<vector>
 5 #include<queue>
 6 #include<stack>
 7 using namespace std;
 8 typedef long long ll;
 9 const int maxn=5e3+5,INF=1e9;
10 struct Edge{
11     int from,to,cap,flow,cost;
12     Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}
13 };
14 struct MCMF{
15     int n,s,t;
16     vector<Edge> edges;
17     vector<int> G[maxn];
18     int inq[maxn],d[maxn],p[maxn],a[maxn];
19     ll flow,cost;
20     void init(int n){
21         this->n=n;
22         flow=0,cost=0;
23         for(int i=0;i<n;i++)G[i].clear();
24         edges.clear();
25     }
26 
27     void AddEdge(int from,int to,int cap,int cost){
28         edges.push_back(Edge(from,to,cap,0,cost));
29         edges.push_back(Edge(to,from,0,0,-cost));
30         G[from].push_back(edges.size()-2);
31         G[to].push_back(edges.size()-1);
32     }
33 
34     bool spfa(int s,int t){
35         for(int i=0;i<n;i++)d[i]=INF;
36         memset(inq,0,sizeof(inq));
37         d[s]=0;inq[s]=1;p[s]=0;a[s]=INF;
38         queue<int>Q;
39         Q.push(s);
40         while(!Q.empty()){
41             int u=Q.front();Q.pop();
42             inq[u]=0;
43             for(int i=0;i<G[u].size();i++){
44                 Edge& e=edges[G[u][i]];
45                 if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){
46                     d[e.to]=d[u]+e.cost;
47                     p[e.to]=G[u][i];
48                     a[e.to]=min(a[u],e.cap-e.flow);
49                     if(!inq[e.to]){Q.push(e.to);inq[e.to]=1;}
50                 }
51             }
52         }
53         if(d[t]==INF)return false;
54         flow+=a[t];cost+=d[t]*a[t];
55         int u=t;
56         while(u!=s){
57             edges[p[u]].flow+=a[t];
58             edges[p[u]^1].flow-=a[t];
59             u=edges[p[u]].from;
60         }
61         return true;
62     }
63     ll Mincost(int s,int t){
64         while(spfa(s,t));
65         return cost;
66     }
67 }mcmf;
68 
69 int N,p,m,f,n,s,r[maxn];
70 void add(int k,int r){
71     mcmf.AddEdge(0,k,INF,p);
72     mcmf.AddEdge(2*N+2,k+N,r,0);
73     mcmf.AddEdge(k,2*N+3,r,0);
74     if(k+1<=N)mcmf.AddEdge(k+N,k+1+N,INF,0);
75     if(k+m<=N)mcmf.AddEdge(k+N,k+m,INF,f);
76     if(k+n<=N)mcmf.AddEdge(k+N,k+n,INF,s);
77 }
78 int main(){
79 //    freopen("e:\in.txt","r",stdin);
80     scanf("%d%d%d%d%d%d",&N,&p,&m,&f,&n,&s);
81     for(int i=1;i<=N;i++)scanf("%d",&r[i]);
82     mcmf.init(2*N+4);
83     mcmf.AddEdge(2*N,2*N+1,INF,0);
84     mcmf.AddEdge(2*N+1,0,INF,0);
85     for(int i=1;i<=N;i++){
86         add(i,r[i]);
87     }
88     printf("%lld
",mcmf.Mincost(2*N+2,2*N+3));
89     return 0;
90 }

二分图做法：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<vector>
 5 #include<queue>
 6 #include<stack>
 7 using namespace std;
 8 typedef long long ll;
 9 const int maxn=5e3+5,INF=1e9;
10 struct Edge{
11     int from,to,cap,flow,cost;
12     Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}
13 };
14 struct MCMF{
15     int n,s,t;
16     ll flow,cost;
17     vector<Edge> edges;
18     vector<int> G[maxn];
19     int inq[maxn],d[maxn],p[maxn],a[maxn];
20 
21     void init(int n){
22         flow=0,cost=0;
23         this->n=n;
24         for(int i=0;i<n;i++)G[i].clear();
25         edges.clear();
26     }
27 
28     void AddEdge(int from,int to,int cap,int cost){
29         edges.push_back(Edge(from,to,cap,0,cost));
30         edges.push_back(Edge(to,from,0,0,-cost));
31         G[from].push_back(edges.size()-2);
32         G[to].push_back(edges.size()-1);
33     }
34 
35     bool spfa(int s,int t,ll &flow,ll &cost){
36         for(int i=0;i<n;i++)d[i]=INF;
37         memset(inq,0,sizeof(inq));
38         d[s]=0;inq[s]=1;p[s]=0;a[s]=INF;
39         queue<int>Q;
40         Q.push(s);
41         while(!Q.empty()){
42             int u=Q.front();Q.pop();
43             inq[u]=0;
44             for(int i=0;i<G[u].size();i++){
45                 Edge& e=edges[G[u][i]];
46                 if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){
47                     d[e.to]=d[u]+e.cost;
48                     p[e.to]=G[u][i];
49                     a[e.to]=min(a[u],e.cap-e.flow);
50                     if(!inq[e.to]){Q.push(e.to);inq[e.to]=1;}
51                 }
52             }
53         }
54         if(d[t]==INF)return false;
55         flow+=a[t];cost+=d[t]*a[t];
56         int u=t;
57         while(u!=s){
58             edges[p[u]].flow+=a[t];
59             edges[p[u]^1].flow-=a[t];
60             u=edges[p[u]].from;
61         }
62         return true;
63     }
64     ll Mincost(int s,int t){
65         while(spfa(s,t,flow,cost));
66         return cost;
67     }
68 }isap;
69 
70 int N,p,m,f,n,s,r[maxn];
71 void add(int k,int r){
72     isap.AddEdge(0,k,r,0);
73     isap.AddEdge(0,k+N,INF,p);
74     isap.AddEdge(k+N,2*N+1,r,0);
75     if(k+1<=N)isap.AddEdge(k,k+1,INF,0);
76     if(k+m<=N)isap.AddEdge(k,k+m+N,INF,f);
77     if(k+n<=N)isap.AddEdge(k,k+n+N,INF,s);
78 }
79 int main(){
80 //    freopen("e:\in.txt","r",stdin);
81     scanf("%d%d%d%d%d%d",&N,&p,&m,&f,&n,&s);
82     isap.init(2*N+2);
83     int r;
84     for(int i=1;i<=N;i++){
85         scanf("%d",&r);
86         add(i,r);
87     }
88     printf("%lld
",isap.Mincost(0,2*N+1));
89     return 0;
90 }