P4015 运输问题【zkw费用流】
2024-08-29 08:03:29
输入输出样例
输入 #1复制
2 3
220 280
170 120 210
77 39 105
150 186 122
输出 #1复制
48500
69140zuixiaofeiyo
说明/提示
1 \leq n, m \leq 1001≤n,m≤100
思路
这题不应该算是个紫题吧。。
没啥坑，也很容易想到最大费用流就是把所有边转换为负边权后的最小费用流
建图也很好想
CODE
#include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl using namespace std;
typedef long long LL; template<class T>inline void read(T &res)
{
char c;T flag=;
while((c=getchar())<''||c>'')if(c=='-')flag=-;res=c-'';
while((c=getchar())>=''&&c<='')res=res*+c-'';res*=flag;
} const int MAXN = 2e3 + ;
const int inf = 0x3f3f3f3f; int N, M; namespace zkw{
struct Edge{
int to, val, cost;
Edge *next, *ops;
Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
}; Edge *head[MAXN << ]; void BuildGraph(int u, int v, int w, int c) {
head[u] = new Edge(v, w, c, head[u]);
head[v] = new Edge(u, , -c, head[v]);
head[u]->ops = head[v]; head[v]->ops = head[u];
} int s, t, ans, res;
int dis[MAXN << ];
bool vis[MAXN << ];
void init() {
memset(dis, 0x3f, sizeof(dis));
memset(vis, false, sizeof(vis));
s = , t = , ans = , res = ;
}
bool Spfa() {
memset(vis, false, sizeof vis);
memset(dis, 0x3f, sizeof dis);
deque<int> q;
q.push_back(s);
vis[s] = true; dis[s] = ;
while (!q.empty()) {
int u = q.front(); q.pop_front(); vis[u] = false;
for (Edge *e = head[u]; e; e = e->next) {
int v = e->to;
if (e->val > && dis[u] + e->cost < dis[v]) {
dis[v] = dis[u] + e->cost;
if (!vis[v]) {
vis[v] = true;
if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return dis[t] < inf;
} int Dfs(int u, int flow) {
if (u == t) {
vis[u] = true;
res += flow;
return flow;
}
int used = ; vis[u] = true;
for (Edge *e = head[u]; e; e = e->next) {//当前弧就不加了
int v = e->to;
if ((!vis[v] || v == t) && e->val && dis[u] + e->cost == dis[v]) {
int mi = Dfs(v, min(e->val, flow - used));
if (mi) {
e->val -= mi;
e->ops->val += mi;
ans += e->cost * mi;
used += mi;
}
if (used == flow) break;
}
}
return used;
} void Work() {
res = ; ans = ;
while (Spfa()) {
vis[t] = true;
while (vis[t]) {
memset(vis, false, sizeof vis);
Dfs(s, inf);
}
}
}
} namespace zkw2{
struct Edge{
int to, val, cost;
Edge *next, *ops;
Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
}; Edge *head[MAXN << ]; void BuildGraph(int u, int v, int w, int c) {
head[u] = new Edge(v, w, c, head[u]);
head[v] = new Edge(u, , -c, head[v]);
head[u]->ops = head[v]; head[v]->ops = head[u];
} int s, t, ans, res;
int dis[MAXN << ];
bool vis[MAXN << ];
void init() {
memset(dis, 0x3f, sizeof(dis));
memset(vis, false, sizeof(vis));
s = , t = , ans = , res = ;
}
bool Spfa() {
memset(vis, false, sizeof vis);
memset(dis, 0x3f, sizeof dis);
deque<int> q;
q.push_back(s);
vis[s] = true; dis[s] = ;
while (!q.empty()) {
int u = q.front(); q.pop_front(); vis[u] = false;
for (Edge *e = head[u]; e; e = e->next) {
int v = e->to;
if (e->val > && dis[u] + e->cost < dis[v]) {
dis[v] = dis[u] + e->cost;
if (!vis[v]) {
vis[v] = true;
if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return dis[t] < inf;
} int Dfs(int u, int flow) {
if (u == t) {
vis[u] = true;
res += flow;
return flow;
}
int used = ; vis[u] = true;
for (Edge *e = head[u]; e; e = e->next) {//当前弧就不加了
int v = e->to;
if ((!vis[v] || v == t) && e->val && dis[u] + e->cost == dis[v]) {
int mi = Dfs(v, min(e->val, flow - used));
if (mi) {
e->val -= mi;
e->ops->val += mi;
ans += e->cost * mi;
used += mi;
}
if (used == flow) break;
}
}
return used;
} void Work() {
res = ; ans = ;
while (Spfa()) {
vis[t] = true;
while (vis[t]) {
memset(vis, false, sizeof vis);
Dfs(s, inf);
}
}
}
} int a[], b[];
int val[][];
int val2[][]; signed main() {
read(M);
read(N);
zkw::init();
zkw :: s = ; zkw :: t = M + N + ;
int s = , t = M + N + ;
for ( int i = ; i <= M; ++i ) {
read(a[i]);
zkw::BuildGraph(s, i, a[i], );
}
for ( int i = ; i <= N; ++i ) {
read(b[i]);
zkw::BuildGraph(i + M, t, b[i], );
}
for ( int i = ; i <= M; ++i ) {
for ( int j = ; j <= N; ++j ) {
read(val[i][j]);
val2[i][j] = -val[i][j];
zkw::BuildGraph(i, j + M, inf, val[i][j]);
}
}
zkw :: Work();
cout << zkw::ans << endl;
zkw2::init();
zkw2 :: s = ; zkw2 :: t = M + N + ;
s = , t = M + N + ;
for ( int i = ; i <= M; ++i ) {
zkw2::BuildGraph(s, i, a[i], );
}
for ( int i = ; i <= N; ++i ) {
zkw2::BuildGraph(i + M, t, b[i], );
}
for ( int i = ; i <= M; ++i ) {
for ( int j = ; j <= N; ++j ) {
zkw2::BuildGraph(i, j + M, inf, val2[i][j]);
//printf("u:%d v:%d val2[i][j]:%d\n",i, j + M, val2[i][j]);
}
}
zkw2::Work();
cout << - zkw2::ans << endl;
return ;
}
#include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl
using namespace std;
typedef long long LL;
template<class T>inline void read(T &res)
{
char c;T flag=;
while((c=getchar())<''||c>'')if(c=='-')flag=-;res=c-'';
while((c=getchar())>=''&&c<='')res=res*+c-'';res*=flag;
}
const int MAXN = e + ;
const int inf = 0x3f3f3f3f;
int N, M;
namespace zkw{
struct Edge{
int to, val, cost;
Edge *next, *ops;
Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
};
Edge *head[MAXN << ];
void BuildGraph(int u, int v, int w, int c) {
head[u] = new Edge(v, w, c, head[u]);
head[v] = new Edge(u, , -c, head[v]);
head[u]->ops = head[v]; head[v]->ops = head[u];
}
int s, t, ans, res;
int dis[MAXN << ];
bool vis[MAXN << ];
void init() {
memset(dis, 0x3f, sizeof(dis));
memset(vis, false, sizeof(vis));
s = , t = , ans = , res = ;
}
bool Spfa() {
memset(vis, false, sizeof vis);
memset(dis, 0x3f, sizeof dis);
deque<int> q;
q.push_back(s);
vis[s] = true; dis[s] = ;
while (!q.empty()) {
int u = q.front(); q.pop_front(); vis[u] = false;
for (Edge *e = head[u]; e; e = e->next) {
int v = e->to;
if (e->val > && dis[u] + e->cost < dis[v]) {
dis[v] = dis[u] + e->cost;
if (!vis[v]) {
vis[v] = true;
if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return dis[t] < inf;
}
int Dfs(int u, int flow) {
if (u == t) {
vis[u] = true;
res += flow;
return flow;
}
int used = ; vis[u] = true;
for (Edge *e = head[u]; e; e = e->next) {//当前弧就不加了
int v = e->to;
if ((!vis[v] || v == t) && e->val && dis[u] + e->cost == dis[v]) {
int mi = Dfs(v, min(e->val, flow - used));
if (mi) {
e->val -= mi;
e->ops->val += mi;
ans += e->cost * mi;
used += mi;
}
if (used == flow) break;
}
}
return used;
}
void Work() {
res = ; ans = ;
while (Spfa()) {
vis[t] = true;
while (vis[t]) {
memset(vis, false, sizeof vis);
Dfs(s, inf);
}
}
}
}
namespace zkw2{
struct Edge{
int to, val, cost;
Edge *next, *ops;
Edge(int to, int val, int cost, Edge *next): to(to), val(val), cost(cost), next(next){}
};
Edge *head[MAXN << ];
void BuildGraph(int u, int v, int w, int c) {
head[u] = new Edge(v, w, c, head[u]);
head[v] = new Edge(u, , -c, head[v]);
head[u]->ops = head[v]; head[v]->ops = head[u];
}
int s, t, ans, res;
int dis[MAXN << ];
bool vis[MAXN << ];
void init() {
memset(dis, 0x3f, sizeof(dis));
memset(vis, false, sizeof(vis));
s = , t = , ans = , res = ;
}
bool Spfa() {
memset(vis, false, sizeof vis);
memset(dis, 0x3f, sizeof dis);
deque<int> q;
q.push_back(s);
vis[s] = true; dis[s] = ;
while (!q.empty()) {
int u = q.front(); q.pop_front(); vis[u] = false;
for (Edge *e = head[u]; e; e = e->next) {
int v = e->to;
if (e->val > && dis[u] + e->cost < dis[v]) {
dis[v] = dis[u] + e->cost;
if (!vis[v]) {
vis[v] = true;
if (!q.empty() && dis[v] < dis[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
}
}
return dis[t] < inf;
}
int Dfs(int u, int flow) {
if (u == t) {
vis[u] = true;
res += flow;
return flow;
}
int used = ; vis[u] = true;
for (Edge *e = head[u]; e; e = e->next) {//当前弧就不加了
int v = e->to;
if ((!vis[v] || v == t) && e->val && dis[u] + e->cost == dis[v]) {
int mi = Dfs(v, min(e->val, flow - used));
if (mi) {
e->val -= mi;
e->ops->val += mi;
ans += e->cost * mi;
used += mi;
}
if (used == flow) break;
}
}
return used;
}
void Work() {
res = ; ans = ;
while (Spfa()) {
vis[t] = true;
while (vis[t]) {
memset(vis, false, sizeof vis);
Dfs(s, inf);
}
}
}
}
int a[], b[];
int val[][];
int val2[][];
signed main() {
read(M);
read(N);
zkw::init();
zkw :: s = ; zkw :: t = M + N + ;
int s = , t = M + N + ;
for ( int i = ; i <= M; ++i ) {
read(a[i]);
zkw::BuildGraph(s, i, a[i], );
}
for ( int i = ; i <= N; ++i ) {
read(b[i]);
zkw::BuildGraph(i + M, t, b[i], );
}
for ( int i = ; i <= M; ++i ) {
for ( int j = ; j <= N; ++j ) {
read(val[i][j]);
val2[i][j] = -val[i][j];
zkw::BuildGraph(i, j + M, inf, val[i][j]);
}
}
zkw :: Work();
cout << zkw::ans << endl;
zkw2::init();
zkw2 :: s = ; zkw2 :: t = M + N + ;
s = , t = M + N + ;
for ( int i = ; i <= M; ++i ) {
zkw2::BuildGraph(s, i, a[i], );
}
for ( int i = ; i <= N; ++i ) {
zkw2::BuildGraph(i + M, t, b[i], );
}
for ( int i = ; i <= M; ++i ) {
for ( int j = ; j <= N; ++j ) {
zkw2::BuildGraph(i, j + M, inf, val2[i][j]);
//printf("u:%d v:%d val2[i][j]:%d\n",i, j + M, val2[i][j]);
}
}
zkw2::Work();
cout << - zkw2::ans << endl;
return ;
}
最新文章
- JHipster框架的简要搭建与说明
- 关于Node.js的总结
- 另类的SQL注入方法
- Oracle中使用Entity Framework 6.x Code-First方式开发
- linux下的挂载点和分区是什么关系
- Chapter 3
- 【英语】Bingo口语笔记(73) - 以tly,tely结尾的误读
- iOS- 自定义UIView （测试block和代理）
- MongoDB 快速入门--中级
- C# 在右下角弹出窗口
- GridView and DropDownList
- poj 3662 Telephone Lines（好题！！！二分搜索+dijkstra）
- c#如何序列化与反序列化json文件
- WebVR认识
- JavaScript获取当前url根目录(路径)
- 说说不知道的Golang中参数传递
- sql server查询数据库的大小和各数据表的大小
- 20169202 2016-2017-2《Windows攻击》
- 【python】如何安装BeautifulSoup4
- Scrapy见面第五天