POJ3422简单费用流
简单 费用
2023-09-11 14:14:00 时间
题意:
给一个n*n的矩阵,从左上角走到右下角,的最大收益,可以走k次,每个格子的价值只能取一次,但是可以走多次。
思路:
比较简单的一个费用流题目,直接拆点,拆开的点之间连接两条边,一条是流量1费用是这个点的价值,另一条是流量k-1费用是0,然后就是当前这个点连接右下方的点,然后在虚拟出超级远点和汇点限流用的,比较简单,不解释了。
#include<stack>
#include<queue>
#include<stdio.h>
#include<string.h>
#define N_node 5100
#define N_edge 200000
#define INF 1000000000
using namespace std;
typedef struct
{
int from ,to ,cost ,flow ,next;
}STAR;
STAR E[N_edge];
int list[N_node] ,tot;
int s_x[N_node] ,mer[N_node];
void add(int a ,int b ,int c ,int d)
{
E[++tot].from = a;
E[tot].to = b;
E[tot].cost = c;
E[tot].flow = d;
E[tot].next = list[a];
list[a] = tot;
E[++tot].from = b;
E[tot].to = a;
E[tot].cost = -c;
E[tot].flow = 0;
E[tot].next = list[b];
list[b] = tot;
}
bool spfa(int s ,int t ,int n)
{
for(int i = 0 ;i <= n ;i ++)
s_x[i] = -INF;
int mark[N_node] = {0};
queue<int>q;
q.push(s);
s_x[s] = 0;
mark[s] = 1;
memset(mer ,255 ,sizeof(mer));
while(!q.empty())
{
int xin ,tou;
tou = q.front();
q.pop();
mark[tou] = 0;
for(int k = list[tou] ;k ;k = E[k].next)
{
xin = E[k].to;
if(s_x[xin] < s_x[tou] + E[k].cost && E[k].flow)
{
s_x[xin] = s_x[tou] + E[k].cost;
mer[xin] = k;
if(!mark[xin])
{
mark[xin] = 1;
q.push(xin);
}
}
}
}
return mer[t] != -1;
}
int M_M_Flow(int s ,int t ,int n)
{
int maxflow = 0 ,maxcost = 0 ,minflow;
while(spfa(s ,t ,n))
{
minflow = INF;
for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])
if(minflow > E[i].flow) minflow = E[i].flow;
for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])
{
E[i].flow -= minflow;
E[i^1].flow += minflow;
maxcost += minflow * E[i].cost;
}
maxflow += minflow;
}
return maxcost;
}
int main ()
{
int n ,k ,i ,j ,Ans ,num;
while(~scanf("%d %d" ,&n ,&k))
{
memset(list ,0 ,sizeof(list)) ,tot = 1;
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
{
scanf("%d" ,&num);
add((i - 1) * n + j ,(i - 1) * n + j + n * n ,num ,1);
add((i - 1) * n + j ,(i - 1) * n + j + n * n ,0 ,k - 1);
}
add(0 ,1 ,0 ,k);
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
{
if(i <= n - 1) add((i - 1) * n + j + n * n ,i * n + j ,0 ,k);
if(j <= n - 1) add((i - 1) * n + j + n * n ,(i - 1) * n + j + 1 ,0 ,k);
}
add(n * n * 2 ,n * n * 2 + 1 ,0 ,k);
Ans = M_M_Flow(0 ,n * n * 2 + 1 ,n * n * 2 + 1);
printf("%d\n" ,Ans);
}
return 0;
}
给一个n*n的矩阵,从左上角走到右下角,的最大收益,可以走k次,每个格子的价值只能取一次,但是可以走多次。
思路:
比较简单的一个费用流题目,直接拆点,拆开的点之间连接两条边,一条是流量1费用是这个点的价值,另一条是流量k-1费用是0,然后就是当前这个点连接右下方的点,然后在虚拟出超级远点和汇点限流用的,比较简单,不解释了。
#include<stack>
#include<queue>
#include<stdio.h>
#include<string.h>
#define N_node 5100
#define N_edge 200000
#define INF 1000000000
using namespace std;
typedef struct
{
int from ,to ,cost ,flow ,next;
}STAR;
STAR E[N_edge];
int list[N_node] ,tot;
int s_x[N_node] ,mer[N_node];
void add(int a ,int b ,int c ,int d)
{
E[++tot].from = a;
E[tot].to = b;
E[tot].cost = c;
E[tot].flow = d;
E[tot].next = list[a];
list[a] = tot;
E[++tot].from = b;
E[tot].to = a;
E[tot].cost = -c;
E[tot].flow = 0;
E[tot].next = list[b];
list[b] = tot;
}
bool spfa(int s ,int t ,int n)
{
for(int i = 0 ;i <= n ;i ++)
s_x[i] = -INF;
int mark[N_node] = {0};
queue<int>q;
q.push(s);
s_x[s] = 0;
mark[s] = 1;
memset(mer ,255 ,sizeof(mer));
while(!q.empty())
{
int xin ,tou;
tou = q.front();
q.pop();
mark[tou] = 0;
for(int k = list[tou] ;k ;k = E[k].next)
{
xin = E[k].to;
if(s_x[xin] < s_x[tou] + E[k].cost && E[k].flow)
{
s_x[xin] = s_x[tou] + E[k].cost;
mer[xin] = k;
if(!mark[xin])
{
mark[xin] = 1;
q.push(xin);
}
}
}
}
return mer[t] != -1;
}
int M_M_Flow(int s ,int t ,int n)
{
int maxflow = 0 ,maxcost = 0 ,minflow;
while(spfa(s ,t ,n))
{
minflow = INF;
for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])
if(minflow > E[i].flow) minflow = E[i].flow;
for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])
{
E[i].flow -= minflow;
E[i^1].flow += minflow;
maxcost += minflow * E[i].cost;
}
maxflow += minflow;
}
return maxcost;
}
int main ()
{
int n ,k ,i ,j ,Ans ,num;
while(~scanf("%d %d" ,&n ,&k))
{
memset(list ,0 ,sizeof(list)) ,tot = 1;
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
{
scanf("%d" ,&num);
add((i - 1) * n + j ,(i - 1) * n + j + n * n ,num ,1);
add((i - 1) * n + j ,(i - 1) * n + j + n * n ,0 ,k - 1);
}
add(0 ,1 ,0 ,k);
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
{
if(i <= n - 1) add((i - 1) * n + j + n * n ,i * n + j ,0 ,k);
if(j <= n - 1) add((i - 1) * n + j + n * n ,(i - 1) * n + j + 1 ,0 ,k);
}
add(n * n * 2 ,n * n * 2 + 1 ,0 ,k);
Ans = M_M_Flow(0 ,n * n * 2 + 1 ,n * n * 2 + 1);
printf("%d\n" ,Ans);
}
return 0;
}
相关文章
- POJ2135 来回最短路(简单费用流)
- POJ2135 来回最短路(简单费用流)
- POJ 2135 简单费用流
- POJ 2135 简单费用流
- google proto buffer安装和简单示例
- 《Spring 3.0就这么简单》——导读
- 基于C++实现的简单的网络应用程序【100010682】
- python3+pyqt5+opencv3简单使用(慢慢更新中)
- JMeter学习-023-JMeter 命令行(非GUI)模式详解(一)-执行、输出结果及日志、简单分布执行脚本
- 函数-memcpy有三种用法,第一种简单,另外两种非常巧妙,你知道吗?
- Unity框架学习_EventManager,简单的事件管理,轻松实现全局的事件系统
- MySQL5.7开启binlog日志,及数据恢复简单示例
- Unity 工具类 之 日志本地化保存和简单界面显示日志
- 我把适配想简单了
- JS简单验证password强度
- 简单工厂模式
- MongoDB + node-mongoskin简单演示样例
- ContentProvider简单介绍
- C# new()约束简单介绍
- 服务器集群自动化部署工具,自动生成 Redis+Tomcat+Nginx相关需要文件,自动配置好依赖jar包和配置文件,简单快速搭建集群环境
- KVM虚拟化(一)—— 介绍与简单使用