UVA - 11090 Going in Cycle!!
Time Limit: 3000MS
Memory Limit: Unknown
64bit IO Format: %lld & %llu
[Submit] [Go Back] [Status]
Description
I I U P C 2 0 06
Problem G: Going in Cycle!!
Input: standard input Output: standard output
You are given a weighted directed graph with n vertices and m edges. Each cycle in the graph has a weight, which equals to sum of its edges. There are so many cycles in the graph with different weights. In this problem we want to find a cycle with the minimum mean.
Input
The first line of input gives the number of cases, N. N test cases follow. Each one starts with two numbers n and m. m lines follow, each has three positive number a, b, c which means there is an edge from vertex a to b with weight of c.
Output
For each test case output one line containing “Case #x: ” followed by a number that is the lowest mean cycle in graph with 2 digits after decimal place, if there is a cycle. Otherwise print “No cycle found.”.
Constraints
- n ≤ 50 - a, b ≤ n - c ≤ 10000000
Sample Input
Output for Sample Input
2 2 1 1 2 1 2 2 1 2 2 2 1 3
Case #1: No cycle found. Case #2: 2.50
Problemsetter: Mohammad Tavakoli Ghinani
const int inf=0x3fffffff;
const int maxn=556;
struct Edge
{
int from,to;double dist;
};
struct bf
{
int n,m;
vector<Edge> edges;
VI G[maxn];
bool inq[maxn];
double d[maxn];
int p[maxn];
int cnt[maxn];
void init(int n)
{
this->n=n;
for(int i=0;i<n;i++)G[i].clear();
edges.clear();
}
void addedge(int from,int to,double dist)
{
edges.pb((Edge){from,to,dist});
m=edges.size();
G[from].pb(m-1);
}
bool negative()
{
queue<int> q;
memset(inq,0,sizeof inq);
memset(cnt,0,sizeof cnt);
for(int i=0;i<n;i++){d[i]=0;inq[i]=1;q.push(i);}
while(!q.empty())
{
int u=q.front();q.pop();
inq[u]=false;
for(int i=0;i<G[u].size();i++)
{
Edge& e=edges[G[u][i]];
if(d[e.to]>d[u]+e.dist){
d[e.to]=d[u]+e.dist;
p[e.to]=G[u][i];
if(!inq[e.to]){
q.push(e.to);
inq[e.to]=true;
if(++cnt[e.to]>n)return true;
}
}
}
}
return false;
}
}solver;
int n,m;
bool test(double x)
{
///cout<<m<<endl;
for(int i=0;i<m;i++)
solver.edges[i].dist-=x;
bool ret=solver.negative();
for(int i=0;i<m;i++)
solver.edges[i].dist+=x;
return ret;
}
int main(){
int T;cin>>T;int kase=1;
while(T--)
{
cin>>n>>m;
solver.init(n);
double ub=0;
for(int i=0;i<m;i++) ///while(m--)
{
int u,v;double w;
scanf("%d%d%lf",&u,&v,&w);u--,v--;
ub=max(ub,w);
solver.addedge(u,v,w);
}
printf("Case #%d: ",kase++);
if(!test(ub+1.0))puts("No cycle found.");
else{
double l=0,r=ub;
while(r-l>1e-3)
{
double m=(l+r)/2;
if(test(m))r=m;else l=m;
}
printf("%.2lf
",l);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
스레드 동기화---귀속 자물쇠Mutex는 귀속 자물쇠(recursive mutex)와 비귀속 자물쇠(non-recursive mutex)로 나눌 수 있다.귀속 가능한 자물쇠는 다시 들어갈 수 있는 자물쇠(reentrantmutex)라고도 할 수...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.