【BZOJ】1877: [SDOI2009]晨跑(最小费用最大流)
最大 最小 BZOJ 费用
2023-09-27 14:22:22 时间
http://www.lydsy.com/JudgeOnline/problem.php?id=1877
费用流做多了,此题就是一眼题。
拆点表示只能经过一次,容量为1,费用为0。
然后再连边即可,跑一次费用流
#include <cstdio> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <algorithm> using namespace std; #define rep(i, n) for(int i=0; i<(n); ++i) #define for1(i,a,n) for(int i=(a);i<=(n);++i) #define for2(i,a,n) for(int i=(a);i<(n);++i) #define for3(i,a,n) for(int i=(a);i>=(n);--i) #define for4(i,a,n) for(int i=(a);i>(n);--i) #define CC(i,a) memset(i,a,sizeof(i)) #define read(a) a=getint() #define print(a) printf("%d", a) #define dbg(x) cout << #x << " = " << x << endl #define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; } inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; } inline const int max(const int &a, const int &b) { return a>b?a:b; } inline const int min(const int &a, const int &b) { return a<b?a:b; } const int N=1010, M=2000000, oo=~0u>>1, pw=410; int ihead[N], cnt=1, d[N], p[N], n, m, vis[N], q[N], front, tail; struct ED { int from, to, cap, w, next; } e[M]; inline void add(const int &u, const int &v, const int &c, const int &w) { e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v; e[cnt].from=u; e[cnt].cap=c; e[cnt].w=w; e[++cnt].next=ihead[v]; ihead[v]=cnt; e[cnt].to=u; e[cnt].from=v; e[cnt].cap=0; e[cnt].w=-w; } inline const bool spfa(const int &s, const int &t) { for1(i, 0, t) d[i]=1000000000, vis[i]=0; vis[s]=1; d[s]=front=tail=0; q[tail++]=s; int u, v, i; while(front!=tail) { u=q[front++]; if(front==N) front=0; for(i=ihead[u]; i; i=e[i].next) if(e[i].cap && d[v=e[i].to]>d[u]+e[i].w) { d[v]=d[u]+e[i].w; p[v]=i; if(!vis[v]) { vis[v]=1, q[tail++]=v; if(tail==N) tail=0; } } vis[u]=0; } return d[t]!=1000000000; } void mcf(const int &s, const int &t) { int ret=0, f, u, flow=0; while(spfa(s, t)) { for(f=oo, u=t; u!=s; u=e[p[u]].from) f=min(f, e[p[u]].cap); for(u=t; u!=s; u=e[p[u]].from) e[p[u]].cap-=f, e[p[u]^1].cap+=f; ret+=d[t]*f; flow+=f; } printf("%d %d\n", flow, ret); } int main() { read(n); read(m); int x, y, c, s=1, t=n; for1(i, 2, n-1) add(i, i+pw, 1, 0); add(s, s+pw, oo, 0); add(t, t+pw, oo, 0); rep(i, m) { read(x); read(y); read(c); add(x+pw, y, 1, c); } mcf(s, t+pw); return 0; }
Description
Elaxia最近迷恋上了空手道,他为自己设定了一套健身计划,比如俯卧撑、仰卧起坐等 等,不过到目前为止,他坚持下来的只有晨跑。 现在给出一张学校附近的地图,这张地图中包含N个十字路口和M条街道,Elaxia只能从 一个十字路口跑向另外一个十字路口,街道之间只在十字路口处相交。Elaxia每天从寝室出发 跑到学校,保证寝室编号为1,学校编号为N。 Elaxia的晨跑计划是按周期(包含若干天)进行的,由于他不喜欢走重复的路线,所以 在一个周期内,每天的晨跑路线都不会相交(在十字路口处),寝室和学校不算十字路 口。Elaxia耐力不太好,他希望在一个周期内跑的路程尽量短,但是又希望训练周期包含的天 数尽量长。 除了练空手道,Elaxia其他时间都花在了学习和找MM上面,所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。
Input
第一行:两个数N,M。表示十字路口数和街道数。 接下来M行,每行3个数a,b,c,表示路口a和路口b之间有条长度为c的街道(单向)。
Output
两个数,第一个数为最长周期的天数,第二个数为满足最长天数的条件下最短的路程长 度。
Sample Input
7 10
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
2 5 5
3 6 6
5 7 1
6 7 1
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
2 5 5
3 6 6
5 7 1
6 7 1
Sample Output
2 11
HINT
对于30%的数据,N ≤ 20,M ≤ 120。
对于100%的数据,N ≤ 200,M ≤ 20000。
Source
相关文章
- 解答私信@YWang521 //C 编写程序,自定义二维整形数组, 数组大小2行10列,用指针的方法求出最大最小和二维数组的平均值,结果输出到屏幕上查看
- 【C++保姆级入门】 最大连号
- poj3422 Kaka's Matrix Travels(最小费用最大流问题)
- 最大熵模型总结
- 最小费用最大流模板
- 网络数据包最大长度 MTU 分片 转发https://blog.csdn.net/singular2611/article/details/52513406
- 面试题-求一个串包括还有一个串的最大子串长度的解法
- 最大熵模型
- **104&111 二叉树的最小、最大深度
- 1224:最大子矩阵 2020-12-02
- UVA 10480 Sabotage (最大流) 最小割边
- POJ 2195 & HDU 1533 Going Home(最小费用最大流)
- 最小公倍数最大可以为多少(主要看计算方法)
- leetcode84最大矩形&&leetcode最大01矩阵
- 初等数论初步——最大公因数
- P1249 最大乘积
- 最大子矩阵的和
- Luogu3381【模板】最小费用最大流
- BZOJ2115 [WC2011]最大XOR和路径
- [LeetCode] 624. Maximum Distance in Arrays 数组中的最大距离
- halcon-dev_open_window_fit_size打开具有给定最小和最大范围的新图形窗口
- halcon-dev_open_window_fit_image打开具有给定最小和最大范围的新图形窗口
- 【Android 内存优化】使用 Memory Analyzer ( MAT ) 工具分析内存 ( MAT 工具使用 | 最大对象 | 类实例个数 | 引用与被引用 | GC Roots 最短链 )