给出一个有L个点P条边的**有向图(有向图记得了,判成无向图一直跑不出数据气死)**,每个点上的点权为F,每条边上的边权为T。请计算存在一个回路使得∑Fi/∑Ti最大。
同样进行二分建图,跑spfa判断是否存在环,由于是正环,所以取反就相当于判负环了。
只不过这题目数据有点水啊(不如说题目描述不够准确),网上很多人从1开始跑环的,但是也有人说是从哪个点都可以,仔细看了一下题目是从起始地点开始,也终于起始点,但是他并没有说起始点是1,而且又说是走过其他一系列的点,也就是说走过任何一个点?这样的话从哪个点开始跑都是没关系的,但是,题目又是给出了边数的啊?!喵喵喵?
还有,输出那里不是说没有环的话就输出0吗?为什么不特判也能过?喵喵喵?!
地址:http://poj.org/problem?id=3621
代码:
Status | Accepted |
---|---|
Time | 360ms |
Memory | 424kB |
Length | 1854 |
Lang | C++ |
(这是bfs版的spfa,dfs版本的可以跑更快)
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <stack> #include <queue> #include <map> #include <set> #include <vector> using namespace std; #define lowbit(x) ((x)&(-x)) #define INF 0x3f3f3f3f #define mem(a,b) memset(a,b,sizeof(a)) #defineGE() printf(">----------\n") #defineIN() freopen("in.txt","r",stdin) #defineOUT() freopen("out.txt","w",stdout) #define MP pair<int, int> typedef long long LL; const int mod=1000000007; const int inf=0x3f3f3f3f; const double pi=acos(-1.0); const double eps=1e-3; const int maxn=5005; int n, m; double dis[maxn]; int inq[maxn], cnt[maxn], w[maxn]; vector<pair<int, int> > E[maxn]; queue<int> Q; bool spfa(double mid){ while(!Q.empty())Q.pop(); for(int i=1;i<=n;i++){ dis[i]=0;inq[i]=1;cnt[i]=1; Q.push(i); } while(!Q.empty()){ int u=Q.front(); Q.pop(); inq[u]=0; for(int i=0;i<E[u].size();i++){ int v=E[u][i].first; double val=w[v]*1.0-1.0*mid*E[u][i].second; if(dis[v]<dis[u]+val){ dis[v]=dis[u]+val; if(++cnt[v]>=n)return 1; if(inq[v])continue; Q.push(v); inq[v]=1; } } } return 0; } int main() { while(~scanf("%d%d", &n, &m)){ for(int i=0;i<=n;i++)E[i].clear(); for(int i=1;i<=n;i++)scanf("%d", &w[i]); int u, v, cost; for(int i=1;i<=m;i++){ scanf("%d%d%d", &u, &v, &cost); E[u].push_back(make_pair(v, cost)); } double l=0, r=1000, mid; while(r-l>eps){ mid=(l+r)/2; if(spfa(mid))l=mid; else r=mid; } if(l==0&&r==1000)printf("0\n"); else printf("%.2f\n", l); } return 0; }