POJ 2135 简单费用流
简单 poj 费用
2023-09-11 14:14:00 时间
题意:
题意是一个人他要从牧场1走到牧场n然后在走回来,每条路径只走一次,问全程的最短路径是多少。
思路:
题意是一个人他要从牧场1走到牧场n然后在走回来,每条路径只走一次,问全程的最短路径是多少。
思路:
这个题目挺简单的吧,首先要保证每条边只能走一次,然后还要要求费用最小,那么我们可以直接跑费用流啊!还有题目说的是去了又回来,这个地方我们可以直接一次跑出两条路径,就是起始的时候的流量是2就行了,然后一遍费用流,然后就wa了,这个题目最坑人的地方就是他的输入叙述,说的什么The starting field, the end field, and the path's length,这个我没猜错应该是说的有向边的意思吧,然后就是wa,改成无向边就行了。别的没啥。
#include<stdio.h>
#include<string.h>
#include<queue>
#define N_node 1000 + 10
#define N_edge 50000 + 200
#define INF 1000000000
using namespace std;
typedef struct
{
int from ,to ,next ,cost ,flow;
}STAR;
STAR E[N_edge];
int list[N_node] ,tot;
int s_x[N_node] ,mer[N_edge];
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};
s_x[s] = 0 ,mark[s] = 1;
queue<int>q;
q.push(s);
memset(mer ,255 ,sizeof(mer));
while(!q.empty())
{
int xin ,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_C_Flow(int s ,int t ,int n)
{
int mincost = 0 ,maxflow = 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;
mincost += minflow * E[i].cost;
}
maxflow += minflow;
}
return mincost;
}
int main ()
{
int n ,m ,i ,a ,b ,c;
while(~scanf("%d %d" ,&n ,&m))
{
memset(list ,0 ,sizeof(list));
tot = 1;
for(i = 1 ;i <= m ;i ++)
{
scanf("%d %d %d" ,&a ,&b ,&c);
add(a ,b ,c ,1);
add(b ,a ,c ,1);
}
add(0 ,1 ,0 ,2);
printf("%d\n" ,M_C_Flow(0 ,n ,n));
}
return 0;
}
相关文章
- 小甲鱼 OllyDbg 教程系列 (十五) : 逆向注册机简单算法
- POJ 3254 简单状压DP
- 快速简单理解i2c标准协议
- Google Earth Engine(GEE)——一个简单的单年逐日时间以sentinel-NO2为例,制作逐日时序图表
- 一个简单奇特的升压电路
- C/C++的“文件包含”处理时头文件被重复包含的问题探究及解决方法(用最简单的例子进行说明)
- 用大数据解放科学家,学术更简单
- kvm安装及简单使用
- 超简单获取快应用摘要值
- 《Android游戏开发详解》——第2章,第2.7节构建一个简单的计数程序
- 大数据学习——kettle的简单使用
- 【开发工具】Git的简单使用,创建版本库、提交代码、更新代码
- 图像切割之(五)活动轮廓模型之Snake模型简单介绍
- 【pyradiomics学习】——安装pyradiomics以及简单示例
- nodejs route的简单使用
- 【Unity笔记】协程Coroutine的简单优化