UVA11090 Going in Cycle!! 【SPFA】
题意:求一个无向图的边权平均值最小的环
思路:假设环中Σwi/t<ans 那变形一下就是Σwi<ans*t → Σ(wi-ans)< 0 这样就可以二分答案做了
#include <stdio.h>
#include <iostream>
#include<queue>
#include <string.h>
#include <algorithm>
#define maxn 90000
#define esp 0.00000001
using namespace std;
int head[maxn],point[maxn],next[maxn],value[maxn];
int now,n,m,x,y,v,inque[maxn];
double dist[maxn];
void add(int x,int y,int v)
{
next[++now]=head[x];
head[x]=now;
point[now]=y;
value[now]=v;
}
int spfa(int s,double x)
{
for(int i=1;i<=n;i++)dist[i]=0x3f3f3f3f;
memset(inque,0,sizeof(inque));
int visit[maxn]={0};
queue<int>q;
q.push(s);
visit[s]=1;
dist[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
visit[u]=0;
for(int i=head[u];i;i=next[i])
{
int k=point[i];
if(double(dist[u]+1.0*value[i]-x)<dist[k])
{
dist[k]=(double)dist[u]+1.0*value[i]-x;
if(visit[k]==0)
{
visit[k]=1;
inque[k]++;
if(inque[k]>n)return 1;
q.push(k);
}
}
}
}
return 0;
}
int main()
{
int t,cas=1,flag=0;
scanf("%d",&t);
while(t--)
{
now=0;
memset(head,0,sizeof(head));
scanf("%d%d",&n,&m);
double l=0,r=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&v);
add(x,y,v);
if(v>r)r=v;
}
printf("Case #%d: ",cas++);
for(int i=1;i<=n;i++)
{
add(n+1,i,0);
}
if(spfa(n+1,r+100)==0){printf("No cycle found.\n");continue;}
while(r-l>esp)
{
double mid=(l+r)/2;
if(spfa(n+1,mid)==1){r=mid;flag=1;}else l=mid;
}
// cout<<spfa(n+1,2.5)<<endl;
printf("%.2f\n",r);
}
return 0;
}
最新文章
- Git分布式版本控制教程
- Android GZIP压缩IO流,优化APP数据传输(一)
- Python资源大全
- EL表达式显示数据取整问题
- git diff
- PHP函数库(other)
- How to use JDBC-Authentication of Spring Boot/Spring Security with Flyway
- Beaglebone Black - 控制 BBB 板上的 LED 灯
- Python 新手常犯错误(第二部分)
- JQuery(一) 入门
- 进程控制之更改用户ID和组ID
- golang中channel的超时处理
- shell 中 2>;&;1 的使用
- memcache memcached 区别
- spring学习总结(mybatis,事务,测试JUnit4,日志log4j&;slf4j,定时任务quartz&;spring-task,jetty,Restful-jersey等)
- Unity3D游戏开发从零单排(四) - 制作一个iOS游戏
- TypeScript入门 2--代码调试
- Android中Activity.this,getApplicationContext(),getBaseContext()和this详解
- SpringMVC mock测试详解
- MIUI12系统怎么样开启Root超级权限的流程