http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2031
题目大意：
给定一个n个点m条边的加权有向图，求平均权值最小的回路。
思路：
用二分法求解。假设答案为mid，只需要判断是否存在平均值小于Mid的回路。怎么判断呢？假设一个包含k条边的回路，回路上各条边的权值为w1,w2……wk，那么平均值小于mid意味着 w1+w2+……wk< k* mid即：
（w1-mid)+(w2-mid)+……(wk-mid)<0
换句话说，只要把图中没一条边a,b的权值w(a,b)变为w(a,b)-mid，在判断图中有没有负权回路。
怎么判断负权回路呢？这就是SPFA的用法了，一个顶点入队列超过n次，就表示有回路。
记住这个不一定是联通的图。所以一开始要把所有的点加入队列。WA找了半天看了别人代码才发现。
---------------2014/01/26----------
想起可以增加一个点0，从该点到所有点的权值为0，那么可以保证改图连通，并且不会破坏负环~~~~~~
代码如下：
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=52;
const int INF=100000000;
struct edge
{
int to;
double val;
int next;
}e[MAXN*MAXN]; int head[MAXN],len,n,m;
void add(int from,int to,double val)
{
e[len].to=to;
e[len].val=val;
e[len].next=head[from];
head[from]=len++;
} bool spfa()
{
double dis[MAXN];
bool vis[MAXN]={0};
int cnt[MAXN]={0};
queue<int> q;
for(int i=1;i<=n;i++) //图可能是非联通的，所以一开始要把全部加入。WA在这里
dis[i]=INF; q.push(0);
vis[0]=cnt[0]=1;
dis[0]=0; while(!q.empty())
{
int cur=q.front();
q.pop();
vis[cur]=false;
for(int i=head[cur];i!=-1;i=e[i].next)
{
int id=e[i].to;
if(dis[cur] + e[i].val < dis[id])
{
dis[id]=dis[cur]+e[i].val;
if(!vis[id])
{
cnt[id]++;
vis[id]=true;
q.push(id);
if(cnt[cur] > n)
return true;
}
}
}
}
return false;
} void change(double x)
{
for(int k=1;k<=n;k++)
for(int i=head[k];i!=-1;i=e[i].next)
e[i].val+=x;
}
bool test(double x)
{
change(-x);
bool ok=spfa();
change(x);
return ok;
} int main()
{
int T;
scanf("%d",&T);
for(int ri=1;ri<=T;ri++)
{
len=0;
memset(head,-1,sizeof(head));
double L=INF,R=0;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int from,to;
double val;
scanf("%d%d%lf",&from,&to,&val);
if(R< val)
R=val;
if(L > val)
L=val;
add(from,to,val);
}
for(int i=1;i<=n;i++)
add(0,i,0); printf("Case #%d: ",ri);
if(!test(R+1))
{
printf("No cycle found.\n");
continue;
} while(R-L > 1e-3) //浮点数判断大小要这样
{
double mid = L + (R-L)/2;
if(test(mid))
R = mid;
else
L = mid;
}
printf("%.2lf\n",R);
} return 0;
}
一开始全部加入队列版本
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=52;
const int INF=100000000;
struct edge
{
int to;
double val;
int next;
}e[MAXN*MAXN]; int head[MAXN],len,n,m;
void add(int from,int to,double val)
{
e[len].to=to;
e[len].val=val;
e[len].next=head[from];
head[from]=len++;
} bool spfa()
{
double dis[MAXN];
bool vis[MAXN];
int cnt[MAXN];
queue<int> q;
for(int i=1;i<=n;i++) //图可能是非联通的，所以一开始要把全部加入。WA在这里
{
dis[i]=INF;
vis[i]=true;
cnt[i]=1;
q.push(i);
} while(!q.empty())
{
int cur=q.front();
q.pop();
vis[cur]=false; for(int i=head[cur];i!=-1;i=e[i].next)
{
int id=e[i].to;
if(dis[cur] + e[i].val < dis[id])
{
dis[id]=dis[cur]+e[i].val;
if(!vis[id])
{
cnt[id]++;
vis[id]=true;
q.push(id);
if(cnt[cur] > n)
return true;
}
}
}
}
return false;
} void change(double x)
{
for(int k=1;k<=n;k++)
for(int i=head[k];i!=-1;i=e[i].next)
e[i].val+=x;
}
bool test(double x)
{
change(-x);
bool ok=spfa();
change(x);
return ok;
} int main()
{
int T;
scanf("%d",&T);
for(int ri=1;ri<=T;ri++)
{
len=0;
memset(head,-1,sizeof(head));
double L=INF,R=0;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int from,to;
double val;
scanf("%d%d%lf",&from,&to,&val);
if(R< val)
R=val;
if(L > val)
L=val;
add(from,to,val);
}
printf("Case #%d: ",ri);
if(!test(R+1))
{
printf("No cycle found.\n");
continue;
} while(R-L > 1e-3) //浮点数判断大小要这样
{
double mid = L + (R-L)/2;
if(test(mid))
R = mid;
else
L = mid;
}
printf("%.2lf\n",R);
} return 0;
}