昨天写好的直接关掉浏览器了没发出去。。
貌似思路很简单？1A。。不过我一开始想的是搜索，有环这个不好判断，而且有可能会多次走环，所以搜索的“最优”性无法体现。把边权赋值为当前从a点到b点换钱之后的价格，用Bellman-Ford算法来找正环。本来bellman是用来找负环，初始化是边权无穷大，而在这里，求可以无限松弛的最大边权路径，故，把边权初始化为无穷小，以正环代表可以挣钱，负环代表赔钱。
#include<iostream>
using namespace std;
int n;
int m;
int s;
double v;
int all;
double dis[101];
struct exchange_points
{
int a; //货币a
int b; //货币b
double ratio;
double costs;
}exc[202];
bool bellman()
{
memset(dis, 0, sizeof(dis)); //这里与bellman的目的刚好相反。初始化为源点到各点距离无穷小
dis[s] = v; //即bellman本用于找负环，求最小路径，本题是利用同样的思想找正环，求最大路径
bool flag;
for (int i = 1; i <= n - 1; i++)
{
flag = false;
for (int j = 0; j<all; j++)
if (dis[exc[j].b] < (dis[exc[j].a] - exc[j].costs) * exc[j].ratio) //寻找最长路径
{ //进行比较的是"某点到自身的权值"和"某点到另一点的权值"
dis[exc[j].b] = (dis[exc[j].a] - exc[j].costs) * exc[j].ratio;
flag = true;
}
if (!flag)
break;
}
for (int k = 0; k<all; k++)
if (dis[exc[k].b] < (dis[exc[k].a] - exc[k].costs) * exc[k].ratio) //正环能够无限松弛
return true;
return false;
}
int main(void)
{
int a, b;
double rab, cab, rba, cba;
while (cin >> n >> m >> s >> v)
{
all = 0;
for (int i = 0; i < m; i++)
{
cin >> a >> b >> rab >> cab >> rba >> cba;
exc[all].a = a;
exc[all].b = b;
exc[all].ratio = rab;
exc[all++].costs = cab;
exc[all].a = b;
exc[all].b = a;
exc[all].ratio = rba;
exc[all++].costs = cba;
}
if (bellman())
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
|