题目链接:http://lightoj.com/volume_showproblem.php?problem=1221
Time Limit: 2 second(s) Memory Limit: 32 MB
Problem Description
A travel company is planning to launch their bus service in a new route. So they conducted a survey and made a list of all possible roads connecting different cities. Each of the roads has a certain amount of income based on current fare. But at the same time, each road has some expenses too (this includes fuel and maintenance cost, staff payments, taxes and tribute to labor union which is recently approved by the Government). The travel company is looking for a cyclic route. That is, the bus will start from any city, then visit one or more cities each exactly once and return to the starting city. The company is also concerned with the profit on the route. In fact the directors of the company have a strict requirement of a profit ratio strictly greater than P. Otherwise they will not launch the service. A profit ratio for a route is the ratio between the total incomes to the total expenses for that route.
One of your friends works in that company and he asks for a little help from you. All you have to do is to determine if there exists such route, so that the company has a profit ratio of P.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a blank line and three integers N, R, P (2 ≤ N ≤ 100, 0 ≤ R ≤ 9900, 1 ≤ P ≤ 100). N, R and P represents number of cities, number of road links and the expected profit ratio respectively. Then R lines follow. Each line contains four integers Ai, Bi, Ii, Ei (0 ≤ Ai, Bi < N, 0 ≤ Ii ≤ 5000, 1 ≤ Ei ≤ 5000). (Ai, Bi) represents directed road link from city Ai to Bi. Ii and Ei are the incomes and expenses of the road link respectively. You may assume that (Ai, Bi) ≠ (Aj, Bj), if i ≠ j and Ai ≠ Bi for any i.
Output
For each case, print the case number and "YES" if there is a cyclic route for which the profit ratio is greater than P or "NO", if there is no such route.
Sample Input
3
5 8 3
0 1 17 8
1 0 10 5
1 2 11 5
1 4 5 3
2 3 13 7
3 1 9 4
4 3 11 1
3 0 11 65 8 3
0 1 17 8
1 0 10 5
1 2 11 5
1 4 5 3
2 3 13 7
3 1 9 4
4 3 11 2
3 0 11 65 8 2
0 1 17 8
1 0 10 5
1 2 11 5
1 4 5 3
2 3 13 7
3 1 9 4
4 3 11 5
3 0 11 6
Output for Sample Input
Case 1: YES
Case 2: NO
Case 3: YES
Note
Dataset is huge. Use faster I/O methods.
Problem solving report:
Description: 旅游公司推出了一种新的旅游路线，这里有n个城市，编号为0~n-1，有m条路线，每行输入u v in out 4个变量，u v 代表编号为u和v的两个城市相连，in代表旅游公司在这条路线上的收入，out代表支出，最开始一行给出一个利润率p(收入/支出)，公司要求找到一条循环路线(即一个环)，使得总利率大于p。
Problem solving: 我们可以根据题意写出这么一条原始的公式:(in[0]+in[1]+...+in[k])/(out[0]+out[1]+...+out[k])>p
即p*(out[0]+out[1]+...+out[k])<(in[0]+in[1]+....in[k]), 故，就是对于这个环中的任意一条边，都要求p*out[i]-in[i]<0，即在图中存在负环。用Spfa算法，因为最短路最多对边松弛n-1次就可以求出来，那么如果一个点入队次数等于n，说明存在负环，即不存在最短路。
Accepted Code:
/*
* @Author: lzyws739307453
* @Language: C++
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int inf = 0x3f3f3f3f;
struct edge {
int u, v, w;
edge() {}
edge(int u, int v, int w) : u(u), v(v), w(w) {}
}e[MAXN * MAXN];
int cnt, n;
bool vis[MAXN];
int f[MAXN], inq[MAXN], dis[MAXN];
void Add(int u, int v, int w) {
e[++cnt] = edge(f[u], v, w);
f[u] = cnt;
}
void init() {
cnt = 0;
memset(f, -1, sizeof(f));
memset(inq, 0, sizeof(inq));
memset(vis, 0, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
}
bool Spfa(int s) {
queue <int> Q;
for (int i = 0; i < n; i++)
Q.push(i);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
vis[u] = false;
for (int i = f[u]; ~i; i = e[i].u) {
int v = e[i].v;
if (dis[v] > dis[u] + e[i].w) {
dis[v] = dis[u] + e[i].w;
if (!vis[v]) {
Q.push(v);
vis[v] = true;
if (++inq[v] >= n)
return true;
}
}
}
}
return false;
}
int main() {
int t, p, m, kase = 0;
scanf("%d", &t);
while (t--) {
init();
scanf("%d%d%d", &n, &m, &p);
for (int i = 0; i < m; i++) {
int u, v, in, out;
scanf("%d%d%d%d", &u, &v, &in, &out);
Add(u, v, p * out - in);
}
printf("Case %d: ", ++kase);
if (Spfa(0))
printf("YES\n");
else printf("NO\n");
}
return 0;
}
京公网安备 11010502036488号