无知 无求

0%

poj2516 Minimum Cost

发表于 分类于 ，

好长时间没更新了哈…前段时间有点忙 后面没事的时候开始更新写写题

很长时间没读英文题面了还有点不适应…题目大意是有n个店员m个仓库k种商品
每个店员需求不同的商品，从不同的仓库调花费也各不相同，问可能的调度中花费最小的，没有则-1

感觉是很普遍的费用流例题，不过也是好长时间不写了…

给了费用矩阵肯定是k种商品每种的n和m之间的全连接写花费，同时为了限制流量店员和仓库都要拆成两个点之间的边就是仓库的容量限制或者店员的商品需求

仔细想了一下发现不太会判断最小费用流的最大流是否满足需求，后来想想可以用限制店员的边来看是否达到要求

写的时候意识到其实不需要拆点，每种商品对应的仓库和店员是分开的已经可以达成要求了

第一遍把所有商品一块计算…tle 后来参考了一下其他人的做法 每个商品分别作为一个小图来计算…会快很多

AC代码

++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
 
const int oo=1e9;//无穷大
const int maxm=200020;//边的最大数量，为原图的两倍
const int maxn=5040;//点的最大数量
 
int node,src,dest,edge;//node节点数，src源点，dest汇点，edge边数
int head[maxn],p[maxn],dis[maxn],q[maxn],vis[maxn];//head链表头，p记录可行流上节点对应的反向边，dis计算距离
 
struct edgenode
{
    int to;//边的指向
    int flow;//边的容量
    int cost;//边的费用
    int next;//链表的下一条边
} edges[maxm];
 
void prepare(int _node,int _src,int _dest);
void addedge(int u,int v,int f,int c);
bool spfa();

 
inline void prepare(int _node,int _src,int _dest)
{
    node=_node;
    src=_src;
    dest=_dest;
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
    memset(p,0,sizeof(p));
    memset(q,0,sizeof(q));
    memset(dis,0,sizeof(dis));
    edge=0;
}
 
void addedge(int u,int v,int f,int c)
{
    edges[edge].flow=f;
    edges[edge].cost=c;
    edges[edge].to=v;
    edges[edge].next=head[u];
    head[u]=edge++;
    edges[edge].flow=0;
    edges[edge].cost=-c;
    edges[edge].to=u;
    edges[edge].next=head[v];
    head[v]=edge++;
}
 
bool spfa()
{
    int i,u,v,l,r=0,tmp;
    for (i=0; i<node; i++) dis[i]=oo;
    dis[q[r++]=src]=0;
    p[src]=p[dest]=-1;
    for (l=0; l!=r; ((++l>=maxn)?l=0:1))
    {
        for (i=head[u=q[l]],vis[u]=false; i!=-1; i=edges[i].next)
        {
            if (edges[i].flow&&dis[v=edges[i].to]>(tmp=dis[u]+edges[i].cost))
            {
                dis[v]=tmp;
                p[v]=i^1;
                if (vis[v]) continue;
                vis[q[r++]=v]=true;
                if (r>=maxn) r=0;
            }
        }
    }
    return p[dest]>=0;
}
 
int spfaflow()
{
    int i,ret=0,delta;
    while (spfa())
    {
        //按记录原路返回求流量
 
        for (i=p[dest],delta=oo; i>=0; i=p[edges[i].to])
        {
            delta=min(delta,edges[i^1].flow);
        }
        for (int i=p[dest]; i>=0; i=p[edges[i].to])
        {
            edges[i].flow+=delta;
            edges[i^1].flow-=delta;
        }
        ret+=delta*dis[dest];
    }
    return ret;
}
int shoper[100][100];
int castle[100][100];
int need[120];
int have[120];
int main()
{
    int N,M,K,start,end;
    while(scanf("%d%d%d",&N,&M,&K),N+M+K)
    {
        memset(shoper,0,sizeof(shoper));
        memset(castle,0,sizeof(castle));
        memset(need,0,sizeof(need));
        memset(have,0,sizeof(have));
        for(int i=1;i<=N;++i)
        {
            for(int j=0;j<K;++j)
            {
                int tmp;
                scanf("%d",&tmp);
                shoper[j][i]=tmp;
                need[j]+=tmp;
            }
        }
        for(int i=1;i<=M;++i)
        {
            for(int j=0;j<K;++j)
            {
                int tmp;
                scanf("%d",&tmp);
                castle[j][i]=tmp;
                have[j]+=tmp;
            }
        }
        int ans=0;
        bool achieve=true;
        for(int i=0;i<K;++i)
        {
            if(need[i]>have[i])
            {
                achieve=false;
            }
            int start=0,end=(N+M)+1;
            prepare(end+1,start,end);
            for(int j=1;j<=N;++j)
            {
                if(shoper[i][j]!=0)
                {
                    addedge(j,end,shoper[i][j],0); 
                }
            }
            for(int j=1;j<=M;++j)
            {
                if(castle[i][j]!=0)
                {
                    addedge(start,N+j,castle[i][j],0);
                }
            }
            for(int j=1;j<=N;++j)
            {
                for(int t=1;t<=M;++t)
                {
                    int tmp;
                    scanf("%d",&tmp);
                    addedge(N+t,j,oo,tmp);
                }
            }
            if(!achieve)
            {
                continue;
            }
            ans+=spfaflow();
        }
        if(!achieve)
        {
            printf("-1\n");
        }
        else
        {
            printf("%d\n",ans);
        }
    }
    return 0;
}