sightseeing专题

ZOJ 1992 Sightseeing Tour

题意：判断混合图欧拉回路思路：（欧拉回路整理参考 http://zhyu.me/acm/zoj-1992-and-poj-1637.html 和 http://blog.csdn.net/zxy_snow/article/details/6230223） 1.无向图：图连通，且图中均为偶度顶点。 2.有向图：图连通，且图中所有顶点出入度相等。 3.混合图：混合图欧拉回

poj 3463 Sightseeing（最短路+次短路）

http://poj.org/problem?id=3463 大致题意：给出一个有向图，从起点到终点求出最短路和次短路的条数之和。解法：用到的数组：dis[i][0]:i到起点的最短路，dis[i][1]:i到起点的严格次短路 vis[i][0],vis[i][1]:同一维的vis数组，标记距离是否已确定 sum[i][0]:i到起点的最短路条数，sum[i][1]:i到

URAL1004 Sightseeing Trip Floyd 最小环

const int maxn=110; int dist[maxn][maxn], map[maxn][maxn]; //最短距离，原图int pre[maxn][maxn]; // pre[i,j]记录最短路里，j前面一个点int path[maxn]; // 答案路径int n, m, num, minc; // num记录path里有多少个点，minc是最短环长度int

洛谷 P2868 观光奶牛Sightseeing Cows 01分数规划 + 最短路判负环

按照惯例，不想写题目大意，转一个 https://blog.csdn.net/liangzihao1/article/details/79716799 题目描述 Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows mu

POJ 1637 Sightseeing tour(混合欧拉回路，网络流)

题意：给你一个图，一些边(有单向边和双向边)问是否有混合欧拉回路(每个边只走一次，起点终点相同). 开始我们可以用点的入度出度检测一下，把双向边任意指定方向，如果某点的出度入度之差为奇数，肯定不会构成欧拉回路的。如果都为偶数，我们就要检测这些双向边能否使得没电入度==出度了。建图：单向边不用考虑，双向边按照开始任意指定的方向建边，容量为1. 一个点如果出度>入度，连边 (源

poj 1734 Sightseeing trip(floyd 最小环)

题目：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=13143 Sightseeing trip Time Limit: 1000MS Memory Limit: 65536KB 64bit IO Format: %I64d & %I64u Submit Status Description

[USACO07DEC]Sightseeing Cows G

题目描述 Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows must decide how best to spend their free time. Fortunately, they have a detaile

poj-3621-Sightseeing Cows-01分数规划+spfa判负环

假如最终的答案是re。那么对每条边进行一定的处理。然后用spfa判断是否出现了负环。如果出现了负环。说明所取的re偏小。就这样二分re。 spfa判断负环的方法是如果某个点入队列超过n次，那么图中存在负环。 #include <iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<

poj-3463-Sightseeing-求次短路

题意是求最短路的数量和比最短路长1的路的数量。此题的本质就是在dij的过程中，可以把一个点走两次。一次最短，一次次短。最后判断即可。 #include <iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<stdlib.h>#include<vector>#include<cmath>

poj-4046-Sightseeing-最短路

首先算出mp[i][j]: 以i为最高点，i到j的最短距离是多少。然后对于每次询问，枚举最高点。结果就为min（mp[i][st]+mp[i][ed]+val[i]）; 但是这个题我用SFL优化了一下。。 #include<stdio.h>#include<string.h>#include<stdlib.h>#include<iostream>#include<algo

URAL1004 Sightseeing Trip(Folyd求最小环，打印路径)

题目： 1004. Sightseeing Trip Time limit: 0.5 second Memory limit: 64 MB There is a travel agency in Adelton town on Zanzibar island. It has decided to offer its clients, besides many other a