首页 > 代码库 > BZOJ1658 [Usaco2006 Mar]Water Slides 滑水
BZOJ1658 [Usaco2006 Mar]Water Slides 滑水
说好的一天题解来啦！
首先作为usaco的silver题，我被虐了。。。调了两天才搞定
最后发现是sort忘了+1（start + cnt1 (+ 1)）还去问管理员要了数据，真是。。。
做法倒不是很难想：
（1）把点分成出度>入度和入度>出度两种
（2）跑一遍网络流
好像会T的很惨。。。然后改进：
发现两条线段交叉一定没有不交叉来得好（就是简单地贪心思想）
于是两类点排序，直接一个一个配对答案一定是最小的。
1 /************************************************************** 2 Problem: 1658 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:32 ms 7 Memory:1040 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 13 using namespace std;14 15 int n, m, ans, cnt1, cnt2, X, Y;16 int deg[15000], start[15000], stop[15000], pos[15000];17 18 int main(){19 scanf("%d%d", &n, &m);20 for (int i = 1; i <= n; ++i)21 scanf("%d", pos + i);22 for (int i = 1; i <= m; ++i){23 scanf("%d%d", &X, &Y);24 ++deg[X], --deg[Y];25 }26 27 for (int i = 1; i <= n; ++i){28 for(; deg[i] > 0; --deg[i]) start[++cnt1] = pos[i];29 for(; deg[i] < 0; ++deg[i]) stop[++cnt2] = pos[i];30 }31 32 sort(start + 1, start + cnt1 + 1);33 sort(stop + 1, stop + cnt2 + 1);34 35 for (int i = 1; i <= cnt1; ++i)36 ans += abs(start[i] - stop[i]);37 printf("%d\n", ans);38 return 0;39 }
BZOJ1658 [Usaco2006 Mar]Water Slides 滑水
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。