【bzoj1877】【SDOI2009】【晨跑】【费用流】
发布日期:2021-11-16 15:38:43
浏览次数:7
分类:技术文章
本文共 1879 字,大约阅读时间需要 6 分钟。
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。题解:拆点保证每个点只走一次,然后费用流即可。
代码:
#include#include #include #define N 500#define M 50010#define inf 2100000000using namespace std;int point[N],ans1,ans2,next[M<<1],pre[N],n,m,T,x,y,c,dis[N],cnt(1),q[N*100];bool f[N];struct use{int st,en,v,c;}e[M<<1];void add(int x,int y,int v,int c){ next[++cnt]=point[x];point[x]=cnt; e[cnt].st=x;e[cnt].en=y;e[cnt].v=v;e[cnt].c=c; next[++cnt]=point[y];point[y]=cnt; e[cnt].st=y;e[cnt].en=x;e[cnt].v=0;e[cnt].c=-c;}bool spfa(){ for (int i=1;i<=T;i++) dis[i]=inf,f[i]=0; int h=0,t=1;q[t]=1;dis[1]=0; while (h dis[u]+e[i].c){ pre[e[i].en]=i; dis[e[i].en]=dis[u]+e[i].c; if (!f[e[i].en]){ q[++t]=e[i].en; f[e[i].en]=1; } } } return dis[T]!=inf;}void isap(){ int mn=inf; for (int i=T;i!=1;i=e[pre[i]].st) mn=min(mn,e[pre[i]].v); for (int i=T;i!=1;i=e[pre[i]].st){ e[pre[i]].v-=mn;e[pre[i]^1].v+=mn;ans2+=mn*e[pre[i]].c; } }int main(){ scanf("%d%d",&n,&m); T=n+n; for (int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&c); add(x+n,y,1,c); } for (int i=2;i<=n-1;i++) add(i,i+n,1,0); add(1,n+1,inf,0); add(n,T,inf,0); while (spfa()){ans1++;isap();} printf("%d %d",ans1,ans2); }
转载地址:https://blog.csdn.net/sunshinezff/article/details/51122952 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月18日 07时36分06秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
python 数据科学 - 【回归分析】 ☞ 线性回归(2)
2019-04-27
python - 批量更改文件名(过滤掉某个字符串)
2019-04-27
python 数据科学 - 【分类模型】 ☞ 决策树
2019-04-27
python - zip、numpy.c 函数
2019-04-27
python 数据科学 - 【分类模型】 ☞ 逻辑回归
2019-04-27
python 数据科学 - 【分类模型】 ☞ 稳健滴 SVM 支持向量机
2019-04-27
python - selenium 处理 alert
2019-04-27
Java - Set、List、Map
2019-04-27
Java - OnlyLady Spider(HttpClient 4.5 )
2019-04-27
Math - 高斯分布(正态分布)
2019-04-27
android学习笔记----简易音乐播放器原理
2019-04-27
Unity编辑器扩展——标签属性Attribute
2019-04-27
Unity中实现拖拽操作
2019-04-27
Unity中的UGUI事件系统
2019-04-27
C#中的常量
2019-04-27
C#中的静态变量与非静态变量
2019-04-27
C#中的ref、out、params关键字
2019-04-27
C#中的多态性
2019-04-27
C#中的命名空间
2019-04-27